Problem6028--简单的烦恼

6028: 简单的烦恼

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

网易云音乐推出了定时关闭播放的功能,假设到了定时关闭播放的时间,当前这首歌还没有播放完,那就把它播放完关闭;如果到了定时关闭的时间,当前歌恰好播放完,那就立即关闭。
小周周在知道网易云这个算法后,想知道如果自己定时 $t$ 时间后关闭播放,那最多能听多长时间的歌。
已知歌单中一共有 $n$ 首歌,并且知道每首歌的播放时间分别是 $a_i$。

Input

第一行一个整数 $T\ (T \leq 23)$,表示数据组数。
在每组输入数据中,第一行有两个正整数,$n\ (n \leq 200),\ t\ (t \leq 80,000)$,分别表示歌单中歌曲的数目,和题目描述中的 $t$。
第二行中有 $n$ 个正整数 $a_i\ (a_i \leq 400)$,表示每首歌曲的时间长度。

Output

对于每组数据,输出一个 ans,表示最多能听多长时间的歌曲。

Sample 1 Input

1
3 7
4 3 2

Sample 1 Output

9
先听第 $2$ 首歌和第 $3$ 首歌,最后播放第 $1$ 首歌,在 $7$ 单位时间后,第 $3$ 首歌还没有播放完,所以要等第 $1$ 首歌播放完,共能听 $9$ 单位时间的歌。

HINT

题目来源:牛客网

EDITORIAL

Source/Category

基础算法 4.121.01背包