Food Festival

City CZ is hosting a large food festival to welcome students from across the nation. Little M loves trying new flavors and does not want to miss any dish. He wants no student to wait for a dish that is already on someone else's table, so he studies how to order the preparation of dishes to minimize the students' waiting time.

The festival has $n$ kinds of dishes. Each student picks one of these kinds when ordering. There are $m$ chefs. After all students have ordered, each chef is assigned a list of dishes to prepare. Then all chefs start cooking at the same time. Each chef cooks in the assigned order and can make only one portion at a time.

Chefs need different amounts of time for the same dish. Let $t_{i,j}$ be the time chef $j$ needs to prepare dish $i$. Dishes are numbered 1 to $n$, and chefs are numbered 1 to $m$.

A student's waiting time is the time from when all chefs start cooking until the student's dish is finished. If the student's dish is the $k$-th dish that some chef prepares, the waiting time is the sum of the preparation times of that chef's first $k$ dishes. The total waiting time is the sum of the waiting times of all students.

exactly $p_i$ students ordered dish $i$. Find the minimum possible total waiting time.

The first line contains two positive integers $n$ and $m$.

The second line contains $n$ positive integers $p_1, p_2, \ldots, p_n$, where $p_i$ is the number of students who ordered dish $i$.

Each of the next $n$ lines contains $m$ nonnegative integers. The $j$-th integer on the $i$-th line is $t_{i,j}$. Adjacent numbers on a line are separated by a single space, and no line has trailing spaces.

Print one line containing the minimum possible total waiting time.

$n \le 40$, $m \le 100$, $p \le 800$, and $t_{i,j} \le 1000$, where $p = \sum p_i$ is the total number of students who ordered.