Problem Background

The data issue has been fixed!

Problem Description

Time is ticking away second by second, yet Xiao F is still deep in thought over the essay topic. It seems he won't be able to finish his essay.

However, Xiao F has a special technique for padding his word count—he keeps breaking lines. This is because the minimum word count requirement for the essay paper is calculated by the number of lines, with each line having $L$ characters.

In other words, reaching $M$ lines (excluding the title) is considered to meet the requirement, meaning there are characters on that line. Note that, due to the essay format requirements, the first line of each paragraph has two characters of indentation.

Now, he has brainstormed $N$ sentences, each with its own length $a_i$—including punctuation marks, without considering situations where periods might be outside the last grid and thus not cause a line break. These sentences have varying degrees of relevance; strongly related sentences are better placed in the same paragraph, while weakly related sentences are better separated by paragraphs. However, for padding the word count, Xiao F can break lines between any two sentences to create paragraphs.

The relevance between sentences is represented in a special way. We know that when grading essays, the scoring points are divided into several main parts, such as the national exam having three parts: foundation, expression, and development, each with the same total score, say $20$ points for the national exam; each part has a minimum score of $0$, meaning even if it's deducted below $0$, it still counts as $0$. Here, our scoring criteria have $K$ parts, each with a full score of $S$ points. Depending on the aspects, Xiao F represents the relevance between two sentences with a $K$-tuple $s_i = (s_{i,1}, s_{i,2}, \cdots, s_{i,K})$, where each number is an integer, and the $j$-th number $s_{i,j}$ indicates:
- If it's a positive number, breaking the sentences $i$ and $i+1$ will deduct $s_{i,j}$ points from the $j$-th part.
- If it's a negative number, not breaking these sentences will deduct $-s_{i,j}$ points from the $j$-th part.
- If it's zero, whether to break these sentences or not has no impact on the score.

Starting from the full score, after calculating the deductions above, a preliminary total score is obtained. After that, for each empty line below the minimum word count line, $C$ points will be deducted, with the total score deducted to $0$ at most.

If Xiao F can achieve a high score on his essay, he can get a thumbs-up from his teacher! Therefore, please help Xiao F design a plan to maximize his score.

Input Format

The first line of input contains $6$ integers, $N, M, L, K, S, C$, corresponding to the content in the problem description.

The second line contains $N$ integers, the $i$-th being $a_i$, the length of each sentence.

The next $N-1$ lines, each containing $K$ integers, the $i$-th line's $j$-th integer represents $s_{i,j}$.

Output Format

Output a single non-negative integer, representing the maximum score you can achieve.

Sample Input and Output

Sample Input #1

4 4 12 2 10 5
5 5 10 4
2 -1
0 0
1 1

Sample Output #1

18

Sample Input #2

2 2 10 1 10 1
1 1
2

Sample Output #2

9

Notes/Hints

Sample 1 Explanation

This is the case without paragraph breaks for Sample 1:

This way, the score is $10 + 9 - 5 = 14$ points.

We find that the word count deduction is too painful, so we must avoid it.

The optimal solution is as follows:

This way, the score is $8 + 10 - 0 = 18$ points.

Sample 2 Explanation

Even though breaking lines can avoid one point of word count deduction, it will correspondingly deduct two points, so it's better not to break.

Subtasks

Subtask $1(21 \mathrm{pts}) : N \leq 10$;

Subtask $2(21 \mathrm{pts}) : K = 1$;

Subtask $3(31 \mathrm{pts}) : N \times a_i \leq 800$;

Subtask $4(77 \mathrm{pts}) :$
- $1 \leq N, M, a_i \leq 200$
- $3 \leq L \leq 200$
- $1 \leq K \leq 5$
- $0 \leq S, C, |s_{i, j}| \leq 200$

见题面 Input 部分

见题面 Output 部分