<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

494. Journal
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



There's an article of N words, with the i-th word consisting of Li 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, ·s, N-th. The location for the i-th word is determined by the following rules:
The word is placed in a block of Li consecutive unoccupied character positions in the same row.
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.)
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.)
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 final 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.

Input
The input file contains several test cases. The first line of the file contains T (), 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 ≤ C ≤ W), followed by the description of the text of the article as N integers L1, L2, ·s, LN (1 ≤ Li ≤ 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 file does not exceed .

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

Example(s)
sample input
sample output
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

<|response|>
## 1) Abridged problem statement (concise)

You have **N words** in order, word *i* has length **Li** (1 ≤ Li ≤ W). A page has fixed width **W** characters and unlimited rows. Text is laid out greedily:

- Each word occupies **Li consecutive free cells in one row**.
- Between two consecutive words placed in the **same row**, there must be **at least 1 empty cell** (a mandatory space).
- Each next word must be placed **not earlier** than the previous (top to bottom, left to right).
- Among all valid placements, choose the **earliest** one.

Before text layout, you place one **illustration rectangle** of size **R × C** anywhere; its cells become occupied. Then the greedy text layout runs.

A row is “used” if it has at least one occupied cell (illustration or text).  
For each test case, choose the illustration placement minimizing the **number of used rows**.

---

## 2) Key observations

1. **Greedy layout is deterministic** once obstacles are fixed.  
   After placing the illustration, the text placement is fully determined by the greedy “earliest possible” rule.

2. The illustration only matters by its **column position** and **which consecutive R rows** it occupies.  
   For a fixed left column `col`, in any row covered by the illustration the free space is split into:
   - left segment width `gapL = col`
   - blocked segment width `C`
   - right segment width `gapR = W - col - C`

3. For any contiguous free segment width `s`, we often need:  
   “Starting at word index `v`, how many consecutive words fit into width `s` with 1 space between words?”  
   Call this function `fit(v, s)` returning the **first word index not placed**.

4. For a fixed `col`, one “illustrated row” acts like a **jump function** on word indices:
   ```
   next(v) = fit( fit(v, gapL), gapR )
   ```
   i.e., fill left segment as much as possible, then fill right segment.

   After **R illustrated rows**, the word index becomes `next^R(v)` (apply `next` R times).

5. We must evaluate many `next^R(v)` queries fast.  
   Using binary lifting is possible, but in this problem (tight time limit) a very fast method is to use **memoized path compression** (union-find-like): cache for each `v` the result after a certain number of steps.

6. We only need to consider illustration top rows aligned with **starts of rows in the baseline layout without illustration**.  
   Compute `row_start[row]`: which word begins each row in the normal layout (no illustration). Trying illustration start at each such row is sufficient for optimality in this approach (matches the reference solution).

---

## 3) Full solution approach

For each test case:

### A) Precompute `fit(v, s)` for all `v` and `s` in **O(N·W)**

We build a table:
- `len_next[v][s]` = the first word index not placed after filling a segment of width `s`, starting from word `v`.

Then:
- If `s < L[v]`, nothing fits ⇒ `fit(v,s)=v`.
- Otherwise `fit(v,s)=len_next[v][s]`.

This avoids per-query binary search.

**How to fill `len_next[v][s]`:**
For each starting `v`, as `s` increases, we can extend how many words fit using a simple “gap counter” (as in the provided code).

We only need `s ≤ W-C` (max free segment width in illustrated rows), but storing up to `W` is fine.

---

### B) Compute baseline row starts without illustration

Simulate the normal greedy layout (no illustration) and record:
- `row_start[row]`: word index that starts at column 0 in that row.
- `num_lines`: last used row index in baseline (0-based).

We need a helper `advance(v, prevPos)` to compute where word `v` starts given the previous word’s start position, following the standard greedy wrap rule.

---

### C) For each illustration column `col`, compute effects of R illustrated rows

For each possible `col` from `0..W-C`:

1. `gapL = col`, `gapR = W - col - C`
2. Define `next(v) = fit(fit(v, gapL), gapR)`
3. Need `next^R(v)` quickly for many `v` values: use **path compression memoization**:

Maintain arrays:
- `comp[v].steps`: for how many steps this cache is valid
- `comp[v].result`: the word index after that many steps

A recursive function `jump(v, steps)`:
- if cached, reuse/extend
- else compute one `next(v)` and recurse

This is fast in practice and matches the editorial/reference.

4. For each baseline row `j` (0..num_lines):
   - starting word is `row_start[j]`
   - after R illustrated rows: `end = jump(row_start[j], R)`
   - update a DP-like best state `best[end]` meaning:
     “we can reach word index `end` after using `j + R` rows so far”.

There is a subtle adjustment when `end == N`: if text finishes exactly there, the last illustrated row might not need to be counted as used by text; the reference solution uses `j + R - (end==N)`.

---

### D) Finish with normal layout DP propagation

Now `best[i]` stores the best-known cursor position (row, col) before placing word `i`.  
We propagate forward using the normal `advance()`:

For `i = 0..N-1`:
- `best[i+1] = min(best[i+1], advance(i+1, best[i]))`

Finally, `best[N].row + 1` is the minimal number of used rows.

---

### Complexity

Per test case:
- Precompute `len_next`: **O(N·W)**
- For each `col` in `0..W-C`:
  - path compression reset: O(N)
  - process O(#baseline rows) queries; jumps are fast due to compression

Designed to pass under very tight limits with low constants.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, w, r, c;
vector<int> lens;

void read_case() {
    cin >> n >> w >> r >> c;
    lens.assign(n + 1, 0);
    for (int i = 0; i < n; i++) cin >> lens[i];
    lens[n] = 0; // sentinel word of length 0 simplifies boundary handling
}

void solve_case() {
    // ------------------------------------------------------------
    // 1) Precompute fit(v, s) via table len_next[v][s] in O(N*W)
    // len_next[v][s] = first word index NOT placed after filling
    // a contiguous segment of length s starting from word v.
    //
    // We only need s up to (w - c) (largest free segment in a row with illustration),
    // but we allocate (w+1) for simplicity.
    // ------------------------------------------------------------
    int max_seg = w - c;
    vector<vector<int>> len_next(n + 1, vector<int>(w + 1, n));

    for (int v = 0; v <= n; v++) {
        // With exactly lens[v] cells, we can place word v (if v<n) and stop.
        int nxt = min(n, v + 1);
        if (lens[v] <= w) len_next[v][lens[v]] = nxt;

        // As we increase available space, keep track of "extra gap"
        // after placing the current packed words. Once gap is enough to
        // place "1 mandatory space + next word", we extend nxt.
        int gap = 0;
        for (int s = lens[v] + 1; s <= max_seg; s++) {
            gap++;
            if (nxt < n && gap >= 1 + lens[nxt]) {
                nxt++;
                gap = 0;
            }
            len_next[v][s] = nxt;
        }
        // For s > max_seg, values are unused in illustrated rows;
        // but keeping default 'n' is fine since we won't query them.
    }

    auto fit = [&](int v, int space) -> int {
        // If already done or first word doesn't fit, no progress.
        if (v == n || space < lens[v]) return v;
        return len_next[v][space];
    };

    // ------------------------------------------------------------
    // 2) advance(): normal greedy layout transition without illustration
    //
    // We store a "cursor" as pair(row, col_start_of_prev_word).
    // To place word v (1..n):
    // - move to end of previous word + (space if not last),
    // - if it doesn't fit, wrap to next row.
    // ------------------------------------------------------------
    auto advance = [&](int v, pair<int,int> prev) -> pair<int,int> {
        int row = prev.first;
        int col = prev.second + lens[v - 1] + (v < n ? 1 : 0); // +1 space unless last word
        if (col + lens[v] > w) { // doesn't fit in current row
            row++;
            col = 0;
        }
        return {row, col};
    };

    // ------------------------------------------------------------
    // 3) Simulate baseline layout (no illustration) to get row_start[]
    // row_start[row] = word index starting at column 0 in that row.
    // ------------------------------------------------------------
    vector<int> row_start(n + 1, 0);
    pair<int,int> cur = {0, 0};
    int num_lines = 0; // last used row index (0-based) in baseline
    for (int j = 1; j <= n; j++) {
        cur = advance(j, cur);
        if (cur.second == 0) row_start[cur.first] = j;
        if (j == n - 1) num_lines = cur.first;
    }

    // ------------------------------------------------------------
    // 4) For each illustration column, compute next^R(v) via path compression
    // next(v) for one illustrated row:
    //   v1 = fit(v, gapL) then v2 = fit(v1, gapR)
    // ------------------------------------------------------------
    struct Comp { int result = 0, steps = 0; };
    vector<Comp> comp(n + 1);

    auto make_compress = [&](int gapL, int gapR) {
        fill(comp.begin(), comp.end(), Comp{});

        auto impl = [&, gapL, gapR](auto&& self, int v, int steps) -> int {
            if (v == n || steps == 0) return v;

            if (comp[v].steps) {
                // We already computed something from v for some previous query.
                // Extend it if needed.
                if (comp[v].result != v) {
                    comp[v].result = self(self, comp[v].result, steps - comp[v].steps);
                }
            } else {
                // First time: compute one "illustrated row jump"
                int nxt = fit(fit(v, gapL), gapR);
                comp[v].result = (nxt != v) ? self(self, nxt, steps - 1) : nxt;
            }
            comp[v].steps = steps;
            return comp[v].result;
        };

        return [impl](int v, int steps) { return impl(impl, v, steps); };
    };

    // best[i] = best known cursor position (row, col) before placing word i
    // We minimize lexicographically: smaller row is better; if tie, smaller col.
    vector<pair<int,int>> best(n + 1, {n + r + 5, 0});

    // Try all illustration left columns
    for (int col = 0; col + c <= w; col++) {
        int gapL = col;
        int gapR = w - col - c;

        auto jump = make_compress(gapL, gapR);

        // Try starting illustration at each baseline row j
        for (int j = 0; j <= num_lines; j++) {
            int start_word = row_start[j];
            int end_word = jump(start_word, r);

            // After using R illustration rows starting at row j,
            // we are ready to place end_word at row j+R (0-based indexing).
            // Adjustment when end_word==n matches reference solution.
            best[end_word] = min(best[end_word], {j + r - (end_word == n), 0});
        }
    }

    // Propagate remaining normal layout from best states
    for (int i = 0; i < n; i++) {
        best[i + 1] = min(best[i + 1], advance(i + 1, best[i]));
    }

    // Answer: last row index + 1
    cout << best[n].first + 1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        read_case();
        solve_case();
    }
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
sys.setrecursionlimit(1_000_000)

def solve_case(n, w, r, c, lens_in):
    # Add sentinel length 0 at index n
    lens = lens_in + [0]
    max_seg = w - c

    # ------------------------------------------------------------
    # 1) Precompute len_next[v][s] for fit(v, s)
    # len_next[v][s] = first word index NOT placed after filling width s
    # starting from word v, with 1 mandatory space between words.
    # ------------------------------------------------------------
    len_next = [[n] * (w + 1) for _ in range(n + 1)]

    for v in range(n + 1):
        nxt = min(n, v + 1)
        lv = lens[v]
        if lv <= w:
            len_next[v][lv] = nxt

        gap = 0
        for s in range(lv + 1, max_seg + 1):
            gap += 1
            if nxt < n and gap >= 1 + lens[nxt]:
                nxt += 1
                gap = 0
            len_next[v][s] = nxt

    def fit(v, space):
        if v == n or space < lens[v]:
            return v
        return len_next[v][space]

    # ------------------------------------------------------------
    # 2) advance(): normal greedy placement transition without illustration
    # prev = (row, col_start_of_previous_word)
    # v is 1..n
    # ------------------------------------------------------------
    def advance(v, prev):
        row, col_prev = prev
        col = col_prev + lens[v - 1] + (1 if v < n else 0)
        if col + lens[v] > w:
            return (row + 1, 0)
        return (row, col)

    # ------------------------------------------------------------
    # 3) Baseline simulation to get row_start[]
    # ------------------------------------------------------------
    row_start = [0] * (n + 1)
    cur = (0, 0)
    num_lines = 0
    for j in range(1, n + 1):
        cur = advance(j, cur)
        if cur[1] == 0:
            row_start[cur[0]] = j
        if j == n - 1:
            num_lines = cur[0]

    # ------------------------------------------------------------
    # 4) Per-column path compression jump for next^R
    # comp_steps[v], comp_res[v] cache "after comp_steps[v] steps from v, end at comp_res[v]"
    # ------------------------------------------------------------
    comp_steps = [0] * (n + 1)
    comp_res = [0] * (n + 1)

    def make_jump(gapL, gapR):
        for i in range(n + 1):
            comp_steps[i] = 0
            comp_res[i] = 0

        def jump(v, steps):
            if v == n or steps == 0:
                return v

            if comp_steps[v] != 0:
                if comp_res[v] != v:
                    comp_res[v] = jump(comp_res[v], steps - comp_steps[v])
            else:
                nxt = fit(fit(v, gapL), gapR)
                comp_res[v] = jump(nxt, steps - 1) if nxt != v else nxt

            comp_steps[v] = steps
            return comp_res[v]

        return jump

    # best[i] = best (row, col) before placing word i
    INF = n + r + 10
    best = [(INF, 0)] * (n + 1)

    # Try all illustration columns
    for col in range(0, w - c + 1):
        gapL = col
        gapR = w - col - c
        jump = make_jump(gapL, gapR)

        for j in range(0, num_lines + 1):
            start_word = row_start[j]
            end_word = jump(start_word, r)
            candidate = (j + r - (1 if end_word == n else 0), 0)
            if candidate < best[end_word]:
                best[end_word] = candidate

    # Propagate remaining text normally
    for i in range(0, n):
        cand = advance(i + 1, best[i])
        if cand < best[i + 1]:
            best[i + 1] = cand

    return best[n][0] + 1

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t = data[0]
    idx = 1
    out = []
    for _ in range(t):
        n, w, r, c = data[idx:idx+4]
        idx += 4
        lens = data[idx:idx+n]
        idx += n
        out.append(str(solve_case(n, w, r, c, lens)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()
```

If you want, I can also provide a short correctness argument (why the `next(v)` modeling matches the greedy placement exactly, and why the final DP propagation produces the minimum).