1 부터 N 까지 번호가 붙은 도시들이 있다.

각 도시에는 자신보다 큰 번호를 갖고 있는 모든 도시로의 직항로가 있고, 각 항로에는 마일리지 점수가 주어진다.

도시 1부터 정해진 수(k)만큼의 도시를 방문하면서 얻을 수 있는 총 마일리지 점수의 최대 값을 구하는 프로그램을 작성하시오. 단, 도시의 총수는 100 을 넘지 않고, k 는 N 보다 작다.

그림은 4 개의 도시와 그 사이의 가능한 항로 및 마일리지 점수의 한 예를 보여준다.

도시 1 에서 시작하여 두개의 도시(k = 2) 를 방문해야 한다면 총 마일리지 점수를 최대화 하는 방법은 1 -> 2 -> 3 순으로 방문하는 것이고 그 총 합은 23( 12 + 11)이 된다.

입력 형식

• 첫째 줄에는 도시의 총 수(N)와 방문해야 할 도시 수(k)가 주어지고, 이 후의 각 줄에는 각 도시에서 도달할 수 있는 모든 항로의 마일리지 점수들이 주어진다. 즉
• 둘째 줄에는 도시 1 에서 시작하는 N-1 개 항로의 마일리지 점수들,
• 셋째 줄에는 도시 2 에서 시작하는 N-2 개 항로의 마일리지 점수들,
• 네째 줄에는 도시 N-3 개 항로로 가는 마일리지 점수가 주어진다.

출력 형식

총 마일리지 점수의 최대값을 출력한다.

입출력 예

입력

4 2 
12 13 8 
11 6 
9 

출력

23

출처:연세대 정올기출