컴퓨터

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

당신은 연속한 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년 동안 컴퓨터를 보유하는 최소 비용을 한 줄에 출력한다.