Preparing NOJ

水獭

1500ms 65536K

Description:

某只水獭酷爱动漫,但是看动画片是很耗时间的,以至于没时间刷题了都。于是,他给她下了个限定,每天只能看T秒的动画片。但是,她今天想看的动画片很多很多,目测在时限内肯定看不完了,只好先计划一下,在时限内看的尽可能多。
水獭想看的动漫有N部,其中每一部都有若干集(第1集、第2集……)这些剧集的观看顺序是不可以调换的,即看完第1集才能看第2集,看完第1、2集后才能看第3集。虽然不能调换顺序,但是她可以选择看到任意一集后放弃这部作品而不用将该部的所有剧集看完。
还要注意的两点:
1、每一集都会完整的看完而不会中途间断。
2、“时限内看得尽可能多”,这是以“集”为单位进行评判的。
那么,请计算出她最多可以看多少集动漫呢?

Input:

第一行包含一个正整数Q,表示有Q组测试数据(1≤Q≤10);
每组测试数据包含若干行,第一行包含两个正整数N和T,分别表示N部动漫作品(1≤N≤20)和T秒的时限(1≤T≤43200);
接下来N行,第i行先包含一个正整数Ki,表示第i部动漫有Ki集(1≤Ki≤20),紧跟着Ki个正整数Cj(1≤Cj≤5000),依次表示第1、2……集的时长(秒)。

Output:

每组测试数据对应一行输出,每行输出仅包含一个整数,即水獭在时限内最多可以看动漫的集数。

Sample Input:

1
2 15
3 5 5 5
5 10 1 1 1 1

Sample Output:

5

Note:

本题由旧版NOJ导入,来源:7A

Info

NOJ

Provider NOJ

Code NOJ2000

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet