11410번 - 칙칙폭폭

도시 1에서 시작해서 도시 N에 도착하는 기차가 있다.  이 기차는 도시의 번호가 증가하는 순서대로 방문한다. 도시 1에서 도시 2로, 도시 3으로, ..., 도시 N으로 이동한다. 기차에는 최대 P명의 사람이 탈 수 있다. 

도시 i에서 출발해 도시 j로 도착하려고 하는 사람은 사람은 총 A_i,j명이 있다. 또, 이때 1인당 기차 요금은 C_i,j이다.

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

사람은 역에서만 내릴 수 있으며, 자기가 내리려고 하는 역에서만 내릴 수 있다.

첫째 줄에 역의 개수 N과 기차의 정원 P가 주어진다. (1 ≤ N ≤ 50, 1 ≤ P ≤ 100)

둘째 줄부터 N-1개의 줄에는 기차를 타려고 하는 사람의 수 A_i,j가 주어진다. i번째 줄의 j번째 숫자는 도시 i에서 도시 i+j로 가려고 하는 사람의 수이다. (0 ≤ A_i,j ≤ 100)

그 다음 줄부터 N-1개의 줄에는 기차 요금 C_i,j가 주어진다. i번째 줄의 j번째 숫자는 도시 i에서 도시 i+j로 가는 1인당 기차 요금이다. (1 ≤ C_i,j ≤ 100)

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

도시 1에서 1->2로 가는 사람 2명, 1->3으로 가는 사람 2명, 1->4로 가는 사람 1명을 태운다. 이제 기차는 5*2+3*2+4*1 = 20원을 벌었다.

도시 2에서 1->2로 가는 사람 2명을 내려주고, 2->3으로 가는 사람 4명을 태운다. 기차는 20 + 6*4 = 44원을 벌었다.

도시 3에서 1->3으로 가는 사람 2명과 2->3으로 가는 사람 4명을 내려준다. 그 다음, 3->4로 가는 사람 6명을 태운다. 기차는 44+1*6 = 50원을 벌었다.

도시 4에 도착했다. 모든 사람을 내려준다.