To welcome students from all over the country, CZ City hosted a grand Food Festival.

As a foodie who loves trying new things, Xiao M naturally did not want to miss this feast. He quickly tasted all the food at the festival. However, the desire to try new things is hard to satisfy. Although all the dishes were delicious and the chefs cooked quickly, Xiao M still felt it was unbearable that there were dishes on other people's tables that were not on his own. So, Xiao M began to study the problem of cooking order, specifically, arranging a cooking order to minimize the waiting time for the students.

Xiao M discovered that there are $n$ different types of dishes at the Food Festival. Each time a student orders, they can choose one of these dishes. There are a total of $m$ chefs to prepare these dishes. After all students have finished ordering, the cooking tasks are assigned to each chef. Then, each chef starts cooking at the same time. The chefs prepare the dishes in the requested order, and they can only prepare one serving at a time.

In addition, Xiao M discovered another interesting fact—although these $m$ chefs can all prepare all $n$ types of dishes, the preparation time for the same dish may differ among different chefs. He numbered the dishes $1, 2, \dots, n$ and the chefs $1, 2, \dots, m$, and denoted the time it takes for chef $j$ to prepare dish $i$ as $t_{i,j}$.

Xiao M believes that: the waiting time for each student is the total length of time from when all chefs start cooking until their own dish is completed. In other words, if a student's dish is the $k$-th dish prepared by a certain chef, their waiting time is the sum of the preparation times of the first $k$ dishes by that chef. The total waiting time is the sum of the waiting times of all students.

Now, Xiao M has found the ordering information for all students—there are $p_i$ students who ordered dish $i$ ($i = 1, 2, \dots, n$). He wants to know what the minimum total waiting time is.

Input

The first line contains two positive integers $n$ and $m$, representing the number of dish types and the number of chefs.

The second line contains $n$ positive integers, where the $i$-th number is $p_i$, representing the number of people who ordered dish $i$.

The following $n$ lines each contain $m$ non-negative integers. The $j$-th number in the $i$-th of these $n$ lines is $t_{i,j}$, representing the time required for chef $j$ to prepare dish $i$.

Adjacent numbers in each line are separated by a single space, and there are no extra spaces at the end of the lines.

Output

Output a single integer, the minimum total waiting time.

Examples

Input 1

3 2
3 1 1
5 7
3 6
8 9

Output 1

47

Note

Chef 1 prepares 1 serving of dish 2 first, then 2 servings of dish 1. The waiting times for the 3 students who ordered these 3 dishes are $3$, $3+5=8$, and $3+5+5=13$.

Chef 2 prepares 1 serving of dish 1 first, then 1 serving of dish 3. The waiting times for the 2 students who ordered these 2 dishes are $7$ and $7+9=16$.

The total waiting time is $3+8+13+7+16=47$.

Although dish 1 and dish 3 are faster to prepare by chef 1, if all these dishes were prepared by chef 1, the total waiting time would actually be longer. If we follow the approach above, adjusting 1 serving of dish 1 and 1 serving of dish 3 to be prepared by chef 2 ensures that chef 2 is not idle, resulting in a shorter total waiting time.

It can be proven that there is no better ordering scheme.

Constraints

For 100% of the data, $n \le 40$, $m \le 100$, $p \le 800$, $t_{i,j} \le 1000$ (where $p = \sum p_i$, the total number of students ordering food).

The values of $n$, $m$, and $p$ for each test case are as follows: