Boss
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

NIO is a big boss. He will now dispatch his N employees to K cities. And he must send exactly e_i employees to the i-th city. NIO has no redundant employees which means,



The cost of sending the i-th employee to the j-th city is . NIO wants to know the minimum cost of the dispatch.

输入描述:

The first line contains two integers  and  --- the number of employees and the number of the cities. 

The second line contains K integers --- the number of employees for i-th city.

The following N lines each contain K integers --- the cost of sending the i-th employee to the j-th city.

输出描述:

One integer represent the minimum cost.
示例1

输入

复制
5 2
1 4
1 1 
4 3 
4 5 
2 1 
3 2

输出

复制
11
示例2

输入

复制
10 8
1 1 1 2 2 1 1 1
6 10 5 6 5 4 9 2 
7 8 8 6 1 4 9 5 
7 4 6 2 5 6 9 1 
8 4 5 3 10 5 10 1 
8 1 7 3 5 9 10 1 
6 10 6 4 10 6 8 7 
10 8 9 4 8 9 5 1 
10 4 5 3 8 7 10 1 
7 3 2 8 1 2 2 10 
6 10 2 5 9 1 6 1

输出

复制
26