Find Max Value (Matrix Compression)

Choose exactly x elements from an n×n matrix, with at most factor[i] from row i, to maximize the total. Output −1 if x elements cannot be chosen; output 0 when x=0.

输入格式

The first line contains n x (1≤n≤1000, 0≤x≤n²); the second line contains n values factor (0..n); the next n lines contain the matrix, with values 1..10⁹.

输出格式

Output a single integer, the answer required by the problem.

样例 1

输入：

3 5
2 1 3
6 8 3
5 10 6
1 1 5

输出：

30

样例 2

输入：

1 1
0
3

输出：

-1

样例 3

输入：

1 0
1
9

输出：

0

样例说明

Example 1: choose 8 and 6 from the first row, 10 from the second, and 5 and 1 from the third, which respects every row limit: 5 items with a total of 30. Example 2: the only row has limit 0, so the required 1 item cannot be chosen; output −1. Example 3: 0 items are required, and the empty selection sums to 0.