3074 : 서울에서 경산까지
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 69 회
- 시도횟수
- 241 회
문제
배우 한정올 씨는 이번 여름에 서울에서 경산까지 자선 여행을 하면서 모금활동을 진행할 계획이다.
자선 여행에서 거쳐 가게 될 도시의 개수와 순서는 미리 정해져 있으며,
자선 여행은 서울에서 시작하여 각 도시를 정해진 순서대로 단 한 번씩 방문한 후 경산에서 끝난다.
서울을 제외한 도시의 개수를 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분이다.
위와 같이 각 구간별로 도보 및 자전거로 이동하는 경우 걸리는 시간과 모금액이 주어질 때,
제한시간 이내로 서울에서 경산까지 여행하면서 모금할 수 있는 최대 금액을 찾는 프로그램을 작성하시오.
(제한시간 이내에 여행하는 방법은 항상 존재한다.)
입력형식
출력형식
입력 예3 1650 500 200 200 100 800 370 300 120 700 250 300 90 |
출력 예660 |
입력 예4 3000 1000 2000 300 700 1100 1900 400 900 900 1800 400 700 1200 2300 500 1200 |
출력 예5900 |
입력 예3 600 500 150 200 1000 100 835 200 324 200 125 300 900 |
출력 예2735 |