题目背景

数据的锅修好了！

题目描述

时间在一秒一秒地减少着，然而小 F 仍对着作文题冥思苦想。看起来，他又写不完作文了。

然而，小 F 有一种特殊的凑字数技巧——不停换行。这是因为，作文纸每行 $L$ 个字，而最低字数限制是以行数来计算的。

也就是说，只要写到了 $M$ 行（不含标题）即认为时满足要求，写到意味着这一行上有字。注意，由于作文格式要求，每段首行会有两个字符的缩进空格。

现在，他已经构思好了 $N$ 句话，每句话有着自己的长度 $a_i$ ——包括标点符号，不考虑因句号等在最后一格之外而不换行的情况。这几句话的关联或强或弱，关联强的更适合放在一段，关联弱的更适合分段，然而因为凑字数小 F 可以对任意两句话之间进行换行以分段。

关联关系会用一种特殊的方式来表示。我们知道，作文改卷时会将作文的得分点划分为几个主要部分，比如全国卷分为基础，表达，发展三个部分；每个部分拥有着相同的总分，比如对于全国卷来说是 $20$ 分；每个部分的最低均为 $0$ 分，也就是说哪怕扣到 $0$ 以下也算 $0$ 分。在这里，我们的评分标准有 $K$ 个部分，每个部分有 $S$ 分的满分。根据方面的不同，小 F 将两句话的关联关系用一个 $K$ 元组 $s_i = (s_{i,1}, s_{i, 2}, \cdots, s_{i, K})$ 表示，其中每个数都是整数，第 $j$ 个数 $s_{i, j}$ 表示：

• 如果是正数，那么表示拆开 $i, i + 1$ 这两句话会导致第 $j$ 部分得分扣 $s_{i, j}$ 分 。
• 如果是负数，那么表示不拆开这两句话第 $j$ 部分得分扣 $-s_{i, j}$ 分。
• 如果为 0，那么表示是否拆开这两句话对得分没有影响。

从满分开始，在计算完上面的扣分之后可以得到一个初步的总分。在这之后，最低字数线上每空一行，会扣 $C$ 分字数分，总分扣至 0 为止。

如果能够拿到高分作文，小 F 就可以得到老师的大拇指！所以，请你帮小 F 设计出一种方案以最大化得分。

输入格式

输入第一行为 $6$ 个整数，$N, M, L, K, S, C$，对应题目描述里的内容。

输入第二行为 $N$ 个整数，第 $i$ 个为 $a_i$，即每句话的长度。

接下来 $N - 1$ 行，每行 $K$ 个整数，第 $i$ 行第 $j$ 个表示 $s_{i, j}$。

输出格式

输出一行一个非负整数，表示你所求得的最大得分。

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

18

2 2 10 1 10 1
1 1
2

9

提示

样例 1 解释

这是样例 1 不分段的情况：

这样做，得分是 $10 + 9 - 5 = 14$ 分。

我们发现，字数分太痛了，于是我们一定要去避免它。

最优解如下：

这样做，得分是 $8 + 10 - 0 = 18$ 分。

样例 2 解释

即使换行可以避免一分字数扣分，但是相应地会扣掉两分，所以不如不换。

子任务

子任务 $1(21 \mathrm{pts}) : N \leq 10$；

子任务 $2(21 \mathrm{pts}) : K = 1$；

子任务 $3(31 \mathrm{pts}) : N \times a_i \leq 800$；

子任务 $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$