最后之作

第 10032 次实验失败之后，被人格修正的Accelerator捡到了 「Misaka Network」的中心司令 LastOrder，此时的LastOrder已经被原先的实验员植入了类似于 "病毒" 的电子信号，一旦电子信号完全传输，整个 「Misaka Network」都会被控制。Accelerator 决定用 「矢量操作」修改这些信号，来拯救整一个「Misaka Network」。

实验员共向LastOrder植入了 n 条长度为 len 的电子信号，每一条信号可以用一个字符集为小写字母的字符串来表示，Accelerator决定把这些信号统一划分成若干非空部分处理，对于每一部分Accelerator可以用「矢量操作」统一修改，第 i 部分能修改的信号数 g(i) 等同于这一部分的 n 个串中不同的串的数量。

例如有 2 段信号 s₁, s₂ ，如果说要划分成 3 部分时，Accelerator会设置 2 个端点 1 ≤ a₁ < a₂< len ，并将这三段信号划分成 s₁[1,a₁], s₁[a₁+1,a₂-1], s₁[a₂, len],s₂[1,a₁], s₂[a₁+1,a₂], s₂[a₂ + 1, len] 六段，其中第一段和第四段在同一部分，第二段和第五段在同一部分，第三段和第六段在同一部分。

Accelerator修改一段信号的方式是从这一段的左端点接入「Misaka Network」，无法避免的是Accelerator的能力会对「Misaka Network」造成伤害，如果Accelerator决定从第 i 个端点接入一段长为 x 的信号，「Misaka Network」将会受到 a_i * x + b_i 的损害，其中 a_i, b_i 是一个可正可负的序列 。

Accelerator定义使用能力以后能造成的正面影响为 ，其中 p 是 Accelerator定的某一个常数，tot 是划分的信号段数，l_i, len_i 分别是每一段信号的左端点和长度。

Accelerator想要尽可能提高拯救Lastorder的成功率，也就是最大化正面影响的值，请你帮他找出一种划分方式，最大化正面影响的值。

第一行三个数 n, len, p。
接下来一行，共 len 个数，第 i 个数表示 ai。
接下来一行，共 len 个数，第 i 个数表示 bi。
接下来 n 行，每行一个长度为 len 的字符串，表示一条信号。

输出共一个数，表示最大化的正面影响的值。

5 5 2
5 4 3 2 1
1 -1 1 -1 1
aabbc
bbcca
aaaab
bbaaa
dddaa

16

1 ≤ n x len ≤ 5 x 105, -109 ≤ ai, bi ≤ 109。