Maximizing Composition Score

Consider the following problem. You are given a composition with N sentences. The composition paper has exactly L characters per line, and the composition must have at least M non‐empty lines (excluding the title). In addition, due to format requirements, every paragraph’s first line has a two‐character indent (so only L-2 characters can be written on that line), while the remaining lines have a capacity of L characters. When writing a paragraph, sentences are concatenated in order. A sentence must be placed entirely on one line; if it does not fit in the remaining space of the current line, a new line is started. Note that a line is counted if it has at least one character. The i\textsuperscript{th} sentence has length a(_i) (including punctuation) and it is guaranteed that any sentence placed at the beginning of a paragraph satisfies a(_i) ≤ L-2 and when it is not the first sentence in a line a(_i) ≤ L.

Furthermore, there is a scoring system based on the relationships between consecutive sentences. For each gap between sentence i and i+1 (for 1 ≤ i ≤ N-1), you are given a K-tuple [ s_i = (s_{i,1}, s_{i,2}, \dots, s_{i,K}) ] where each s(_{i,j}) is an integer. The effect on the j\textsuperscript{th} scoring part is as follows:

• If s({i,j}) is positive, then splitting (i.e. putting sentence i and sentence i+1 in different paragraphs) incurs a penalty of s({i,j}) points in that part.
• If s({i,j}) is negative, then not splitting them (keeping them in the same paragraph) incurs a penalty of (-s{i,j}) points in that part.
• If s(_{i,j}) is zero, there is no effect.

Initially, every part starts with a full score of S; hence the total initial score is K (S). After applying the penalties for every gap according to your choices, you get an intermediate score. Finally, if the written non-empty lines (obtained after formatting the text into paragraphs) are less than M, then for each missing line you deduct C points from the intermediate score. (The total score is never allowed to fall below 0.)

Your task is to decide, for each gap between consecutive sentences, whether to split (start a new paragraph) or not. Splitting between sentences i and i+1 will add a penalty of (\sum_{j=1}^{K}\max(0, s_{i,j})), while not splitting adds a penalty of (\sum_{j=1}^{K}\max(0, -s_{i,j})). Moreover, the formatting of the final text (i.e. how the sentences are regrouped into paragraphs and how many lines are used when the text is laid out according to the line‐width limits and indent rules) influences a further deduction if the total number of lines is less than M.

Formally, if you denote by R the sum of relationship penalties chosen along the N-1 gaps and by L_total the total number of lines after formatting, then the final score is computed as [ \text{Score} = \max\Bigl(0, K,S - R - C,\max(0, M - L_{total})\Bigr). ]

Determine the maximum achievable score by choosing an optimal way to break the sentences into paragraphs. It is guaranteed that an optimal strategy exists such that all sentences are used in order and the formatting rules are followed.

Note: The formatting for each paragraph is done as follows: For a paragraph containing sentences with indices (i, i+1, \dots, j), the first line starts with a 2-character indent and can hold up to (L-2) characters; subsequent lines can hold up to (L) characters. For each sentence, if it does not fit in the current line, start a new line and then place it (without any extra space in between sentences).

inputFormat

The input begins with a line containing six integers:

N L M K S C

where

• N (1 ≤ N ≤ ?) is the number of sentences, • L (L ≥ 3) is the number of characters per line, • M (M ≥ 1) is the minimum number of non-empty lines required (excluding the title), • K (K ≥ 1) is the number of scoring parts, • S (S ≥ 1) is the full score for each part, and • C (C ≥ 1) is the penalty per missing line.

The second line contains N integers representing the lengths a₁, a₂, …, a_N of the sentences. It is guaranteed that any sentence that would start a paragraph satisfies aᵢ ≤ L-2, and every sentence satisfies aᵢ ≤ L when it is not the first item on a line.

Then follow N-1 lines, each containing K integers. The i\textsuperscript{th} of these lines gives the K-tuple s_i = (s₍i,₁₎, s₍i,₂₎, …, s₍i,K₎) describing the relationship between sentence i and sentence i+1.

outputFormat

Output a single integer, the maximum achievable total score according to the rules described. Remember that the final score cannot be negative (if penalties exceed the initial score, output 0).

sample

3 10 4 2 20 5
5 3 4
3 -2
-1 4

33