Under construction

Still being built. Things may change

Study Schedule Planning

Interview

Time limit1sMemory limit1024 MB

Summary
Assign non-negative study hours to N subjects, with a total of at most T, to maximize the summed scores minus the fatigue penalty for the total hours.
Level

Medium5 of 10

Topics
Dynamic programming, Array
Solved
No attempts yet

Problem

Banana, a stage performer, has entered her third year of high school. She wants to attend a prestigious university, but she has spent all her time on acting practice and has never studied for school exams. She decides to get serious and study for the college entrance exam that is TT hours away. Having no study experience, Banana does not know how many hours she should study. Let's make a study schedule for her!

The college entrance exam has NN subjects. Let Si,jS_{i,j} be the score Banana earns for subject ii (1≤i≤N)(1\leq i\leq N) when she studies it for a total of jj (0≤j≤T)(0\leq j\leq T) hours. Following the habits Banana has kept so far, the study time for each subject must be a non-negative integer.

However, human stamina is limited, so studying all day is hard. If she studies for a total of XX (0≤X≤T)(0\leq X\leq T) hours, she gets tired and her total score decreases by DXD_X. The total score can become negative.

You must find the maximum score Banana can get when she studies in the best way, and the study plan that achieves it.

Input

The first line contains NN and TT, separated by a space.

From the second line through the (N+1)(N+1)-th line, the (i+1)(i+1)-th line contains T+1T+1 numbers Si,0,Si,1,⋯ ,Si,TS_{i,0}, S_{i,1}, \cdots, S_{i,T}, separated by spaces. These are the scores for subject ii when studied for jj (0≤j≤T)(0\leq j\leq T) hours.

The (N+2)(N+2)-th line contains T+1T+1 numbers D0,D1,⋯ ,DTD_0, D_1, \cdots, D_T, separated by spaces.

All numbers in the input are integers.

Output

On the first line, print the maximum score scorescore Banana can get.

On the second line, print NN integers A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N separated by spaces, where AiA_i is the number of hours to study subject ii. If several study plans give the maximum score, you may print any of them.

Constraints

  • 1≤N≤1001\leq N\leq 100
  • 1≤T≤1001\leq T\leq 100
  • 0≤Si,j≤10 0000\leq S_{i,j}\leq 10\,000 (1≤i≤N(1 \leq i \leq N; 0≤j≤T)0 \leq j \leq T)
  • Si,j≤Si,j+1S_{i, j} \leq S_{i, j + 1} (1≤i≤N(1 \leq i \leq N; 0≤j<T)0 \leq j < T)
  • 0≤DX≤10 0000\leq D_X\leq 10\,000 (0≤X≤T)(0 \leq X \leq T)
  • DX≤DX+1D_X\leq D_{X+1} (0≤X<T)(0 \leq X < T)
  • 0≤A1+A2+⋯+AN≤T0\leq A_{1}+A_{2}+ \cdots +A_{N}\leq T

Examples1

  1. Example 1

    Input
    3 4
0 4 7 9 10
0 5 9 11 12
0 1 2 4 10
0 3 6 9 12
    Expected output
    4
1 2 0