题目描述

有一篇包含 $N$ 个单词的文章，第 $i$ 个单词由 $L_i$ 个字母组成。现在要把这篇文章排版到一页期刊上。页面每行恰好有 $W$ 个字符位置；为简化问题，可以认为页面能够包含任意多行，并且所有字符宽度相同。

单词按照 $1,2,\ldots,N$ 的顺序依次排版。第 $i$ 个单词的位置按照下面的规则确定：

1. 第 $i$ 个单词必须放在同一行中连续的 $L_i$ 个、当前尚未被占用的字符位置上；
2. 当 $i>1$ 时，第 $i$ 个单词的第一个字符与第 $i-1$ 个单词的最后一个字符，不能处在同一行中相邻的两个位置上。也就是说，如果相邻两个单词位于同一行，它们之间至少要空出一个字符位置；
3. 当 $i>1$ 时，第 $i$ 个单词所占的字符块不能位于第 $i-1$ 个单词所占字符块之前。若字符块 $A$ 所在的行高于字符块 $B$，或者二者位于同一行且 $A$ 在 $B$ 的左侧，则称 $A$ 位于 $B$ 之前；
4. 在满足以上条件的所有位置中，选择最靠前的那个位置放置第 $i$ 个单词。

例如，下面是一篇文章在宽度为 $20$ 的页面上的排版结果：

除了文章之外，页面上还需要放置一幅插图。插图占据一个高为 $R$ 行、宽为 $C$ 列的矩形区域。

插图会在文字排版之前放置，并且可以放在页面上的任意位置，只要整个矩形都位于页面宽度范围之内。插图覆盖的所有字符位置都视为已经被占用。随后，再按照前面给出的规则依次排版所有单词。

如果在插图放置并完成文字排版之后，某一行中至少有一个字符位置被插图或文字占用，那么这一行称为已使用行。

最终使用的行数可能会随着插图位置的不同而变化。下面给出了同一篇文章和同一幅插图的两种放置方式：左图最终使用了 $11$ 行，而右图只使用了 $10$ 行。

请你选择插图的位置，使得最终使用的总行数尽可能少，并输出这个最小值。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据组数，其中 $1\le T\le1000$。

接下来依次给出 $T$ 组测试数据。

每组测试数据首先包含四个整数 $N,W,R,C$，其中：

• $1\le N\le10000$；
• $1\le W,R\le1000$；
• $1\le C\le W$。

随后给出 $N$ 个整数 $L_1,L_2,\ldots,L_N$，其中 $1\le L_i\le W$，表示每个单词的长度。

所有整数之间可以由空格或换行任意分隔。

保证整个输入文件中，所有测试数据的 $N$ 之和不超过 $10000$。

输出格式

对于每组测试数据，输出一行一个整数，表示在最优放置插图的情况下，最终最少需要使用多少行。

样例输入1

1
26 20 3 6
10 7 2 1 4 6 4 4 3 5 3 3
7 6 7 4 2 7 4 10 3 6 5 8 7 7

样例输出1

10