You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

apiadu 是一位策略游戏高手，他正在为一场“石头剪刀布”大赛做准备。

比赛规则如下：apiadu 需要从 $n$ 位潜在的对手中选择一位，并与他进行 $m$ 轮的对决。apiadu 通过赛前侦查，已经精确地知道了自己以及这 $n$ 位对手在未来 $m$ 轮中将要出的手势。

手势用数字表示：0 代表石头，1 代表剪刀，2 代表布。胜负规则为：石头(0)胜剪刀(1)，剪刀(1)胜布(2)，布(2)胜石头(0)。

计分规则也很明确：

• 赢一局，apiadu 获得 $y$ 分。
• 输一局，apiadu 失去 $z$ 分 (即获得 $-z$ 分)。
• 平局，分数不变。

apiadu 的初始分数为 $0$。他希望通过选择最合适的对手，来最大化自己在这 $m$ 轮对决结束后的总得分。请你帮他计算出这个可能的最大得分。

格式

输入格式

第一行包含四个整数 $n, m, y, z$，分别表示对手的数量、比赛的轮数、赢一局的得分和输一局失去的分数。

第二行包含 $m$ 个整数，代表 apiadu 在第 $1$ 到第 $m$ 轮将要出的手势。

接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行代表第 $i$ 位对手在第 $1$ 到第 $m$ 轮将要出的手势。

输出格式

输出一个整数，表示 apiadu 能够获得的最大总得分。

样例

样例输入 #1

2 3 3 2
0 1 2
1 1 0
2 0 1

样例输出 #1

6

样例解释 #1

对于第一个对手，对战的总得分为：$3 + 0 + 3 = 6$。

对于第二个对手，对战的总得分为：$-2 - 2 -2 = -6$。

数据规模

对于 $100\%$ 的测试数据，$1 \leq n, m \leq 1000$，$1 \leq y, z \leq 10^9$。且所有手势均为 0, 1, 2 中的一个。