공부 계획하기

무대소녀 바나나는 고등학교 3학년이 되었다. 명문 대학을 가고 싶은 그녀이지만, 평소 연기 연습만을 하며 내신 공부를 전혀 하지 않았던 바나나는 정신을 차리고 $T$시간 뒤에 있는 수능을 위해 공부하기로 마음먹었다. 그러나 공부 경험이 없는 바나나는 공부를 얼마나 해야 하는지를 알 수 없었다. 바나나를 위해 공부 스케줄을 짜주자!

수능에는 $N$개의 과목이 있다. $i$ $(1\leq i\leq N)$번 과목을 총 $j$ $(0\leq j\leq T)$시간 공부했을 때 받을 수 있는 점수를 $S\_{i,j}$ 라 하자. 바나나가 지켜오던 스케줄에 따라, 각 과목의 공부 시간은 음이 아닌 정수여야 함에 주의하자.

그러나 인간의 체력에 한계가 있기 때문에 하루 종일 공부를 하는 것은 힘들다. 총 $X$ $(0\leq X\leq T)$시간 만큼 공부를 하면 피곤해져서 총 점수가 $D\_{X}$만큼 감소하게 된다. 이로 인하여 점수가 음수가 될 수도 있음에 주의하자.

당신은 최적의 방법으로 공부를 하였을 때 바나나가 얻을 수 있는 최대 점수와 그때의 공부 방법을 구해야 한다.

첫째 줄에는 수능 과목의 수 $N$과 $T$가 공백으로 구분되어 주어진다.

둘째 줄부터 $N+1$번째 줄까지는 $i+1$ $(1\leq i\leq N)$번째 줄에 $i$번째 과목을 $j$ $(0\leq j\leq T)$시간 공부했을 때 받을 수 있는 점수에 대한 $T+1$개의 수 $S\_{i,0}$, $S\_{i,1}$, $\cdots$, $S\_{i,T}$가 공백으로 구분되어 주어진다.

$N+2$번째 줄에는 $T+1$개의 수 $D\_{0}$, $D\_{1}$, $\cdots$, $D\_{T}$가 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 수는 정수이다.

첫째 줄에 바나나가 받을 수 있는 최대 점수 $score$를 출력하라.

둘째 줄에 각 과목 별로 공부해야 하는 시간을 뜻하는 $N$개의 정수 $A\_{1}$, $A\_{2}$, $\cdots$, $A\_{N}$을 공백으로 구분하여 출력하라. 만약 최대 점수를 받는 공부 방법이 여러 가지라면, 그 중 아무거나 출력해도 좋다.

• $1\leq N\leq 100$
• $1\leq T\leq 100$
• $0\leq S\_{i,j}\leq 10\\,000$ $(1 \leq i \leq N$; $0 \leq j \leq T)$
• $S\_{i, j} \leq S\_{i, j + 1}$ $(1 \leq i \leq N$; $0 \leq j < T)$
• $0\leq D\_X\leq 10\\,000$ $(0 \leq X \leq T)$
• $D\_X\leq D\_{X+1}$ $(0 \leq X < T)$
• $0\leq A\_{1}+A\_{2}+ \cdots +A\_{N}\leq T$