Description

There are $n$ students and $m$ study groups. Each student is willing to join only some of the study groups, and any student can join at most $k$ study groups. For each student participating in a study group, the finance office charges a handling fee; different study groups have different fees. If $a$ students join the $i$-th study group, the finance office pays a reward of $C_i \times a^2$ yuan. Subject to making the number of participating students (i.e., the number of distinct students, not the sum over all groups) as large as possible, find the minimum amount of money the finance office must spend.

Input Format

The input consists of multiple lines. The first line contains three positive integers $n, m, k$ separated by spaces.

The next line contains $m$ positive integers, the values of $C_i$.

The third line contains $m$ positive integers, the handling fees $F_i$ required to join each study group.

Then follows an $n$-by-$m$ matrix. If the number at row $i$, column $j$ is 1, then the $i$-th student is willing to join the $j$-th study group; if it is 0, then the student is unwilling.

Output Format

Output a single integer: the minimum expenditure.

3 3 1
1 2 3
3 2 1
111
111
111

-2

Hint

For $100\%$ of the testdata, $0 < n \le 100$, $0 < m \le 90$, $0 < k \le m$, $0 < C_i \le 10$, $0 < F_i \le 100$.

Translated by ChatGPT 5