배우 한정올 씨는 이번 여름에 서울에서 경산까지 자선 여행을 하면서 모금활동을 진행할 계획이다.

자선 여행에서 거쳐 가게 될 도시의 개수와 순서는 미리 정해져 있으며,

자선 여행은 서울에서 시작하여 각 도시를 정해진 순서대로 단 한 번씩 방문한 후 경산에서 끝난다.

서울을 제외한 도시의 개수를 N이라 하자. 이 때 서울에서 두 번째 도시까지 가는 구간을 구간 1,

두 번째 도시부터 세 번째 도시까지 가는 구간을 구간 2와 같이 부르기로 하며,

마지막 목적지인 경산에 도착하는 구간을 구간 N이라 하자.

즉, 구간의 전체 개수는 N이다.

구간 사이의 이동은 도보 혹은 자전거 어느 한 쪽을 이용하게 되는데,

각 구간에는 도보로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원),

자전거로 이동할 때 걸리는 시간(분), 이 때 얻게 되는 모금액(원)이 정해져 있다.

예를 들어, 서울과 경산 사이에 2개의 도시가 있는 다음과 같은 경우(N = 3)를 생각해 보자.

한정올 씨는 전체 모금액을 가능한 많이 얻는 방법을 찾고 싶어 한다.

위의 예에서는 시간이 충분하다면 모든 구간을 도보로 이동하는 것이 모금액을 최대로 하는 방법이며,

모금액은 200+370+250 = 820원, 여행에 걸리는 시간은 500+800+700 = 2,000분이다.

그러나 한정올 씨는 바쁜 스케줄로 인해 자선 여행을 위해 보낼 수 있는 시간이 K분(K는 자연수)으로 한정되어 있다.

위의 예에서 만약 K=1,650이라면,

1, 2번 구간은 도보로 이동하고 3번 구간은 자전거로 이동하여 모금액을 660원으로 하는 것이 가장 좋은 방법이며,

이 때 걸리는 시간은 1,600분이다.

위와 같이 각 구간별로 도보 및 자전거로 이동하는 경우 걸리는 시간과 모금액이 주어질 때,

제한시간 이내로 서울에서 경산까지 여행하면서 모금할 수 있는 최대 금액을 찾는 프로그램을 작성하시오.

(제한시간 이내에 여행하는 방법은 항상 존재한다.)

서울에서 경산까지 timer 1초 memory 128MB

서울에서 경산까지 1초 128MB