老虎和蒜头是好朋友。

老虎最近在研究贪心问题。在老虎学习的贪心书上，有这样一个入门的简单练习：

有一个 $ n $ 个点的无向图，有 $ m $ 个点集 $ V_1 \ldots V_m $ ，第 $ i $ 个点集有一个权值 $ r_i $ 。老虎会按照某个顺序将这些点集排序。随后，老虎按顺序取出点集，并将点集内部的点连边，如果已有边就不连。不妨假设在选择到点集 $ V_i $ 时，新增了 $ e $ 条边，就会产生 $ f(e) \times r_i $ 的收益，而老虎的目标，是最大化收益。

在原本的问题中，$ f(e) = e $ 。但现在的老虎的水平已经有了长足的进步，因此问题也发生了一些变化。具体来说，收益函数 $ f(e) = (ae^2 + be + c) \bmod n $ 。

你能帮老虎求出最大的收益吗？

输入格式

输入的第一行包括两个正整数 $ n, m $ ，表示无向图的点数和点集的数目。

接下来的一行包括三个整数 $ a, b, c $ ，表示收益函数的参数。

接下来的一行包括 $ m $ 个整数 $ r_i $ 。

接下来共 $ m $ 行，每行一个长度为 $ n $ 的 01 字符串。对于第 $ i $ 行的第 $ j $ 个字符来说，若其为 $ 1 $ ，则表示 $ j \in V_i $ ，否则表示点集 $ j \not \in V_i $ 。

输出格式

输出共包括一行一个数，表示最终的答案。

样例一

input

5 3
0 2 1
1 2 1
10100
10011
11110

output

11

样例二

input

6 4
1 2 3
3 2 3 4
000111
100110
101000
001110

output

35

限制与约定

本题共包括 5 个子任务，对于所有子任务，均有 $ 0 \le a, b, c, r_i < n $ 。

Subtask 1(7 分): $ 1 \le n \le 1000, 1 \le m \le 20, a = c = 0 $

Subtask 2(10 分): $ 1 \le n \le 50, 1 \le m \le 7 $

Subtask 3(16 分): $ 1 \le n \le 100, 1 \le m \le 13 $

Subtask 4(33 分): $ 1 \le n \le 2 \times 10^5, 1 \le m \le 15 $

Subtask 5(34 分): $ 1 \le n \le 10^6, 1 \le m \le 20 $

时间限制: 3s

空间限制: 512MB