题目描述

您正在参加编程比赛。比赛的问题数量为 $n$。对于每个问题 $P_i(1 \le i \le n)$ 都有若干子问题。对于第 $i$ 个问题，解决第 $j$ 个子问题后，你将获得的得分为 $s_{i_j}$。

对于每个问题 $i$ ，解决第 $j$ 个子问题必须首先解决第 $j-1$ 个子问题（$j>1$）。

例如，如果一个问题有 3 个子问题，并且子问题指定为 3、6 和 10 分，解决第一个子问题会给你 3 分，那么解决第二个问题会给你 6 分，解决前三个会给你满分 10 分（注意部分分数加起来不等于 19 分）。

你决定从那些看起来很容易解决的问题开始，然后开始处理点数最小的子问题。如果有多个分数相同的子问题，请先处理编号最小的问题。

给定解决每个子问题所需的时间 $t_{i_j}$ 和整个竞赛的时间 $T$ ，你需要求出在比赛结束时你能得到多少分。

如果比赛在解决某个问题的同时结束，则该部分问题也包含在已解决的问题中。

输入格式

第一行两个整数 $n,T$。

第二行 $n$ 个整数 $P_1,P_2,…,P_n$，$P_i$ 代表第 $i$ 个任务有 $P_i$ 个子任务。

接下来 $n$ 行，第 $i$ 行有 $P_i$ 个数，代表第 $i$ 个任务每个子任务的分值。

接下来 $n$ 行，第 $i$ 行有 $P_i$ 个数，代表完成第 $i$ 个任务的每个子任务所需时间。

输出格式

一个整数，代表你能够得到的分值。

输入输出样例

输入#1

3 100
1 2 2
100
15 150
30 200
20
10 30
20 40

输出#1

280

输入#2

3 120
1 2 2
100
15 150
30 200
20
10 30
20 40

输出#2

450

输入#3

2 100
2 3
15 100
3 100 200
10 90
5 40 40

输出#3

18

输入#4

3 75
1 1 1
250
500
1000
100
300
1000

输出#4

0

输入#5

11 300
1 1 2 2 2 3 2 2 2 3 2
30
50
10 60
30 90
20 100
20 40 100
30 110
30 120
40 120
20 40 140
100 150
10
15
10 15
10 20
15 30
15 40 60
40 60
30 50
40 50
10 20 100
100 150

输出#5

430