<|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

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

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

void read() {
    cin >> n >> w >> r >> c;
    lens.resize(n + 1);
    for(int i = 0; i < n; i++) {
        cin >> lens[i];
    }
    lens[n] = 0;
}

void solve() {
    // Given the constraints, we could afford a solution that is O(N*(R+W+C)),
    // or something of this sort. Naively, we could have tried all possible
    // locations for the upper left corner of the image in O((N + R) * C), and
    // then in O(N) checked how many rows this would actually take. To speed
    // this up, we can actually do something very similar - in stead of choosing
    // the full location, let's just choose the column in O(C). Now we can try
    // all possible options for the image starting below the row that ends with
    // word number i. More precisely, we can compute something like next[pos],
    // which corresponds to having our current row ending on word pos equaling
    // the number of the last word after one more row, but with an image here
    // (at the already fixed column). This next[.] can be computed easily in
    // O(log N) with binary search or O(1) with sliding window. Afterwards it's
    // enough to just try every possible position, and then apply
    // next[next[...]] from each position R times, to see where we would end up
    // after R rows. The candidate for the answer is then pref_rows[pos] + R +
    // suff_rows[next^R[pos]+1]. The slowest part here is computing next^R[pos],
    // as we can't afford a O(R) loop. However, we can do binary lifting and do
    // this in O(log R) instead. Overall, this solution would potentially be
    // still slow as it's in O(W * N * (log N + log R)).
    //
    // To speed this up further, we make two key improvements. First, we
    // precompute a table len_next[v][length] for every word v and every
    // available length, storing how many words fit starting from v with that
    // much space, using a sliding window in O(N * W) total, giving O(1) per
    // query instead of O(log N). Second, we replace binary lifting for
    // computing next^R[pos] with path compression similar to union-find. For
    // a fixed column, we need next^R[v] for each starting row's first word
    // v. We process rows j = 0, 1, ..., and for each, follow the chain
    // storing at each visited node both the final result and the number of
    // steps it compressed. When a later query passes through an already-
    // visited node v, it jumps directly to v's stored result and only extends
    // the chain by the remaining steps. Crucially, later rows always reach
    // shared nodes with more remaining steps (since the starting word is
    // closer to v, fewer steps were consumed reaching it), so the chain only
    // ever extends forward. This in practice is very quick and could maybe
    // be shown to be O(N) but I didn't get a clean argument after thinking for
    // a bit.
    //
    // Another option is to think of the tree where the parent of some position
    // is next[pos]. We want to find the K-th parent of each position, which 
    // can actually be done with a stack and a DFS: whenever we enter a node, 
    // we add it to the stack, while when we exit we pop it. It's always enough 
    // to just get the element at position depth(pos)-K, which we can do with 
    // a DFS in O(N).

    vector<vector<int>> len_next(n + 1, vector<int>(w + 1, n));
    for(int v = 0; v <= n; v++) {
        int nxt = min(n, v + 1);
        len_next[v][lens[v]] = nxt;
        for(int k = lens[v] + 1, gap = 0; k <= w - c; k++) {
            gap++;
            if(nxt < n && gap >= 1 + lens[nxt]) {
                nxt++;
                gap = 0;
            }
            len_next[v][k] = nxt;
        }
    }

    auto fit = [&](int v, int space) -> int {
        if(v == n || space < lens[v]) {
            return v;
        }
        return len_next[v][space];
    };

    auto advance = [&](int v, pair<int, int> prev) -> pair<int, int> {
        int col = prev.second + lens[v - 1] + (v < n ? 1 : 0);
        int row = prev.first;
        if(col + lens[v] > w) {
            col = 0;
            row++;
        }
        return {row, col};
    };

    vector<int> row_start(n + 1, 0);
    pair<int, int> cur = {0, 0};
    int num_lines = 0;
    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;
        }
    }

    struct Comp {
        int result = 0, steps = 0;
    };
    vector<Comp> comp(n + 1);

    auto make_compress = [&](int gap_left, int gap_right) {
        fill(comp.begin(), comp.end(), Comp{});
        auto impl = [&, gap_left,
                     gap_right](auto&& self, int v, int steps) -> int {
            if(v == n || steps == 0) {
                return v;
            }
            if(comp[v].steps) {
                if(comp[v].result != v) {
                    comp[v].result =
                        self(self, comp[v].result, steps - comp[v].steps);
                }
            } else {
                int nxt = fit(fit(v, gap_left), gap_right);
                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); };
    };

    vector<pair<int, int>> best(n + 1, {n + r + 1, 0});

    int ans = num_lines + r + 1;
    for(int col = 0; col + c <= w; col++) {
        auto path_compress = make_compress(col, w - col - c);
        for(int j = 0; j <= num_lines; j++) {
            int end = path_compress(row_start[j], r);
            best[end] = min(best[end], {j + r - (end == n), 0});
        }
    }

    for(int j = 0; j < n; j++) {
        best[j + 1] = min(best[j + 1], advance(j + 1, best[j]));
    }

    ans = min(ans, best[n].first + 1);
    cout << ans << '\n';
}

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

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

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

def solve_case(n, w, r, c, lens_input):
    # lens[0..n-1] are real words; lens[n] is sentinel 0
    lens = lens_input[:] + [0]

    # Precompute len_next[v][space] for v in [0..n], space in [0..w]
    # Only spaces up to (w - c) are needed for illustrated segments, but w is small enough.
    len_next = [[n] * (w + 1) for _ in range(n + 1)]
    max_seg = w - c

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

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

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

    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)

    # Compute row_start for the base layout (no illustration)
    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]

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

    # Per-column path compression structure
    class Comp:
        __slots__ = ("result", "steps")
        def __init__(self):
            self.result = 0
            self.steps = 0

    comp = [Comp() for _ in range(n + 1)]

    def make_compress(gap_left, gap_right):
        # Reset memo for this column
        for i in range(n + 1):
            comp[i].result = 0
            comp[i].steps = 0

        def jump(v, steps):
            """Compute next^steps(v) with memoized compression."""
            if v == n or steps == 0:
                return v

            if comp[v].steps != 0:
                # Extend from stored result if needed
                if comp[v].result != v:
                    comp[v].result = jump(comp[v].result, steps - comp[v].steps)
            else:
                nxt = fit(fit(v, gap_left), gap_right)
                comp[v].result = jump(nxt, steps - 1) if nxt != v else nxt

            comp[v].steps = steps
            return comp[v].result

        return jump

    # Try all illustration columns
    for col in range(0, w - c + 1):
        jump = make_compress(col, w - col - c)
        for j in range(0, num_lines + 1):
            end = jump(row_start[j], r)
            candidate = (j + r - (1 if end == n else 0), 0)
            if candidate < best[end]:
                best[end] = candidate

    # Propagate remaining words with normal greedy layout
    for j in range(0, n):
        cand = advance(j + 1, best[j])
        if cand < best[j + 1]:
            best[j + 1] = cand

    return best[n][0] + 1  # row index + 1 => number of used rows


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()
```
