21765_Journa

There's an article of N words, with the i-th word consisting of L_i letters. The article has to be printed in a journal on a page W characters wide (for simplicity, let's assume that the page can contain as many lines as necessary and that all characters have the same width). The algorithm of laying out the text on the page of the journal is as follows. The words are placed in order: 1-st, 2-nd, ... , N-th. The location for the i-th word is determined by the following rules:

1. The word is placed in a block of L_i consecutive unoccupied character positions in the same row.

2. The first character of the i-th word and the last character of the (i-1)-th word can't be in adjacent positions of the same row. (Obviously, this applies only for i > 1.)

3. The block for the i-th word must not stand earlier than the block for the (i-1)-th word. A block A is considered to stand earlier than a block B if A is in a higher row than B or if they are in the same row and A is located to the left from B. (This also applies only for i > 1.)

4. Out of all blocks satisfying to the previous conditions, the earliest one is chosen.

The layout of a sample text on a page 20 characters wide is shown below:

In addition to the article, an illustration has to be placed on the page. The illustration takes up a rectangular area R rows high and C columns wide. The illustration is placed on the page before the text is laid out and it may be placed anywhere on the page. After the illustration is placed, all character positions covered by it are considered occupied and then the text is laid out according to the algorithm described above.

A row on the page is considered used if, after the illustration is placed and the text laid out, at least one character of the row is occupied. The total number of rows used may depend on the position of the illustration. For example, two possible nal layouts of the illustration and the text are shown below, with one using 11 and the other 10 rows:

Given the dimensions of the illustration and a description of the text, place the illustration in a way that minimizes the number of rows occupied by the final layout.

The input file contains several test cases. The first line of the file contains T (1 ≤ T ≤ 1000), the number of test cases. Descriptions of the T test cases follow.

The description of each test case starts with the integers N, W, R, C (1 ≤ N ≤ 10000, 1 ≤ W, R ≤ 1000, 1 ≤ C ≤ W), followed by the description of the text of the article as N integers L₁, L₂, ..., L_N (1 ≤ L_i ≤ W). The numbers may be separated by spaces and/or newlines.

It may be assumed that the sum of values of N over all test cases in the le does not exceed 10000.

For each test case, output a single line containing the minimal number of rows needed to lay out the article.

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

10