컴퓨터

시간 제한1초메모리 제한128 MB

요약

고정 교체비와 임의의 구간별 유지비가 주어질 때, n년 동안 컴퓨터를 소유하는 최소 총비용을 동적 계획법으로 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

누구나 컴퓨터를 좋아하지만, 새 컴퓨터를 사는 것은 늘 금전적으로 부담이 된다. 다행히 편리한 절충안이 있다. 컴퓨터를 새것으로 교체하면 유지비를 아낄 수 있지만, 새 컴퓨터를 살 때마다 고정 비용을 내야 한다.

당신은 연속한 n년 동안 컴퓨터를 보유하려고 한다. 항상 정확히 한 대의 컴퓨터를 보유하며, 1년차에도 반드시 보유해야 하므로 1년차에는 반드시 컴퓨터를 산다. 컴퓨터를 살 때마다 고정 비용 c를 낸다. y년차에 산 컴퓨터를 z년차까지 사용하면(y ≤ z ≤ n), y년차부터 z년차까지 보유하는 데 추가로 유지비 m(y, z)가 든다. z+1년차가 시작될 때 새 컴퓨터로 교체할 수 있다.

n년의 기간 동안 컴퓨터를 보유하는 최소 총비용을 구하라.

입력

입력은 표준 입력으로 주어지며 여러 개의 데이터 집합을 포함할 수 있고, 파일 끝에서 종료된다. 각 데이터 집합은 하나의 인스턴스를 나타낸다. 데이터 집합은 새 컴퓨터를 사는 고정 비용 c로 시작하고, 이어서 연수 n, 그리고 유지비 m(y, z)가 y = 1 … n, z = y … n의 순서로 주어진다(먼저 y = 1에 대한 값들, 그다음 y = 2, 이런 식으로). 숫자 사이에는 공백이 자유롭게 올 수 있으며, 모든 입력은 올바르다.

출력

각 데이터 집합에 대해, n년 동안 컴퓨터를 보유하는 최소 비용을 한 줄에 출력한다.

예제4

예제 1
입력
```
3
3
5 7 50
6 8
10
```
예상 출력
```
19
```
예제 2
입력
```
5
1
10
```
예상 출력
```
15
```
예제 3
입력
```
10
2
1 2
1
```
예상 출력
```
12
```
예제 4
입력
```
1
2
1 100
1
```
예상 출력
```
4
```