칙칙폭폭

도시 1에서 출발해 도시 $N$까지 가는 기차가 있다. 이 기차는 도시 번호가 커지는 순서대로 도시 1, 도시 2, 도시 3, ..., 도시 $N$을 차례로 지난다. 기차에는 한 번에 최대 $P$명이 탈 수 있다.

도시 $i$에서 도시 $j$로 가려는 사람은 모두 $A_{i,j}$명이고, 이 구간의 1인당 요금은 $C_{i,j}$원이다. 승객은 자기가 출발하는 도시에서만 타고, 자기가 내리려는 도시에서만 내린다. 기차는 기다리는 사람 중에서 태울 사람을 자유롭게 고를 수 있고, 한 사람을 일부만 태울 수는 없다.

기차가 올릴 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $N$과 기차의 정원 $P$가 주어진다. ($1 \le N \le 50$, $1 \le P \le 100$)

다음 $N-1$개의 줄에는 사람 수가 주어진다. $i$번째 줄의 $j$번째 수는 도시 $i$에서 도시 $i+j$로 가려는 사람의 수 $A_{i,i+j}$이고, $i$번째 줄에는 수가 $N-i$개 있다. ($0 \le A_{i,j} \le 100$)

그다음 $N-1$개의 줄에는 요금이 주어진다. $i$번째 줄의 $j$번째 수는 도시 $i$에서 도시 $i+j$로 가는 1인당 요금 $C_{i,i+j}$이고, $i$번째 줄에는 수가 $N-i$개 있다. ($1 \le C_{i,j} \le 100$)

$N$이 1이면 두 표 모두 비어 있고, 입력은 첫째 줄로 끝난다.

첫째 줄에 기차가 올릴 수 있는 최대 수익을 출력한다.

첫 번째 예제에서 기차는 다음과 같이 움직일 때 수익이 가장 크다.

도시 1에서 1번 도시에서 2번 도시로 가는 사람 2명, 1번에서 3번으로 가는 사람 2명, 1번에서 4번으로 가는 사람 1명을 태운다. 여기까지 수익은 $5 \times 2 + 3 \times 2 + 4 \times 1 = 20$이다.

도시 2에서 1번에서 2번으로 가는 사람 2명을 내려주고, 2번에서 3번으로 가는 사람 4명을 태운다. 수익은 $20 + 6 \times 4 = 44$가 된다.

도시 3에서 1번에서 3번으로 가는 사람 2명과 2번에서 3번으로 가는 사람 4명을 내려준 뒤, 3번에서 4번으로 가는 사람 6명을 태운다. 수익은 $44 + 1 \times 6 = 50$이 된다.

도시 4에 도착하면 남은 사람을 모두 내려준다. 최종 수익은 50이다.