搬家

题号：NC278307
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定 $n$ 个物品， $m$ 个收纳箱，物品和收纳箱均排成一行，每个收纳箱容量均为 $k$ ，每个物品体积为 $a_i$ 。

初始指定第一个收纳箱，并选择一个起始位置 $i$ ，从第 $i$ 个物品开始按顺序遍历它和它右侧的所有物品，对于每一个遍历的物品：

如果当前物品可以装入目前指定的收纳箱，则将其装入。
反之则指定其右侧的第一个收纳箱，重复第一步。
直到物品被遍历完，或者右侧不存在收纳箱时，停止过程。

问能最多装入多少物品。

输入描述:

第一行一个整数 ，表示数据组数。

对于每组数据，第一行三个整数  。

接下来一行  个整数  。

保证 。

输出描述:

输出  行，每行一个整数表示最多能装入多少物品。

示例1

输入

复制

1
5 2 5
2 3 3 4 4

输出

复制

说明

从第  个物品开始选，第  个盒子装第  个物品和第  个物品，第  个盒子装第  个物品。

从第  个物品开始选，第  个盒子装第  个物品，第  个盒子装第  个物品。

从第  个物品开始选，第  个盒子装第  个物品，第  个盒子装第  个物品。

从第  个物品开始选，第  个盒子装第  个物品，第  个盒子装第  个物品。

从第  个物品开始选，第  个盒子装第  个物品。

所以最多装  个物品。

示例2

输入

复制

1
5 2 4
1 3 1 2 3

输出

复制

说明

从第  个物品开始选，第  个盒子装第  个物品和第  个物品，第  个盒子装第  个物品和第  个物品。

从第  个物品开始选，第  个盒子装第  个物品和第  个物品 ，第  个盒子装第  个物品。

从第  个物品开始选，第  个盒子装第  个物品和第  个物品，第  个盒子装第  个物品。

从第  个物品开始选，第  个盒子装第  个物品，第  个盒子装第  个物品。

从第  个物品开始选，第  个盒子装第  个物品。

所以最多装  个物品。