Minimizing Total Waiting Time at the Food Festival

CZ City is hosting a grand food festival to welcome students from all over the country. As a passionate foodie, Little M quickly sampled every dish at the festival. However, he couldn’t bear the idea that his table lacked some of the delicious dishes already served on others’ tables. Thus, he started to study the order in which dishes are prepared, so that the total waiting time of all students can be minimized.

There are \( n \) different dishes (numbered \(1, 2, \ldots, n\)). Each student orders exactly one dish. In total, for dish \(i\), there are \( p_i \) orders. There are \( m \) chefs (numbered \(1, 2, \ldots, m\)). After the ordering is complete, the preparation tasks are distributed among the chefs. Then, all chefs start cooking simultaneously. Each chef cooks the orders assigned to him in a specified sequence and can prepare only one portion at a time.

All chefs can cook every dish, but the cooking time for dish \(i\) may vary among chefs. In fact, the time needed by chef \(j\) to cook dish \(i\) is \(t_{i,j}\) (in minutes). For any student, if his order is the \(k\)-th dish prepared by a chef, his waiting time is the sum of the preparation times for the first \(k\) orders on that chef. The total waiting time is the sum of the waiting times of all students.

Determine the minimum total waiting time achievable by optimally assigning each dish order to a chef as well as the position (order in the sequence) in which it is cooked. In an optimal assignment, each chef will process his assigned orders in non‐decreasing order of the corresponding cooking times (i.e. in SPT order). Formally, if chef \(j\) has been assigned \(q_j\) orders and a particular order for dish \(i\) is placed at position \(k\) (where \(1 \le k \le q_j\)) in his sequence, then its waiting time is \(k \times t_{i,j}\).

Find the assignment that minimizes the sum of waiting times.

inputFormat

The input begins with two integers \(n\) and \(m\) (the number of dishes and the number of chefs).

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\), where \(p_i\) is the number of orders for dish \(i\).

Then follow \(n\) lines, each containing \(m\) integers. The \(i\)-th line contains \(t_{i,1}, t_{i,2}, \ldots, t_{i,m}\), where \(t_{i,j}\) is the time chef \(j\) takes to cook dish \(i\).

You may assume that the total number of orders \(\sum_{i=1}^{n} p_i\) is reasonably small for simulation.

outputFormat

Output a single integer, the minimum total waiting time.

sample

2 2
1 1
1 2
2 1

2