상수는 Pinball이라는 게임을 좋아합니다. Pinball의 규칙은 다음과 같습니다.

Pinball의 놀이판은 (M+2)행 N열의 정사각형 격자들로 구성된 격자판입니다. 놀이판의 첫 번째 줄은 판의 꼭대기이고, (M+2)번째 줄은 바닥입니다. i번째 행의 j번째 열에 있는 정사각형 격자는 (i,j)로 표현됩니다.

공은 놀이판의 첫 번째 줄에 있는 격자들 중 하나에 나타나서, 바닥을 향해 수직으로 떨어집니다. 다시 말해, 만약 어떤 공이 (1, i) (1 ≤ i ≤ N)에 나타났다면, 이는 (j, i) (2 ≤ j ≤ M+1)을 통과하여, 바닥의 (M+2, i) 격자에 도착할 것입니다. 상수는 공을 성공적으로 되받아 친다면 점수를 얻게 됩니다.

어느 날, 상수는 공을 되받아치기 어렵다는 것을 눈치챘는데, 공이 바닥의 어떤 격자에나 등장할 수 있기 때문입니다. 상수는 아래에 설명된 장치들을 놀이판 위에 적절하게 설치하여 공이 도달할 수 있는 바닥의 격자가 단 하나 있도록 하려고 합니다.

1이상 M 이하의 번호가 붙은 M개의 장치들이 있습니다. 각 장치는 놀이판의 행들과 평행합니다. i (1 ≤ i ≤ M)번째 장치는 (i+1, Ai)부터 (i+1, Bi)까지의 격자들에 위치해 있습니다. 따라서 이 장치는 총 Bi−Ai+1개의 격자들을 덮습니다. 만약 공이 이 장치가 설치되어 있는 격자에 닿는다면, 공은 (i+1, Ci)로 운반될 것입니다. 그 이후, 이동한 공은 Ci번 열을 따라 수직하게 떨어질 것입니다. 하나의 장치는 공과 한 번 이상 상호 작용하지 않을 것입니다.

상수가 i번째 장치를 설치하기 위해서는 Di원을 지불해야 합니다. 상수는 M개의 장치들 중 일부를 골라서 놀이판에 설치하여, 공이 도달할 수 있는 바닥의 격자가 단 하나 존재하도록 할 것입니다. 상수는 장치들을 효율적으로 설치하여 총 비용을 줄이고자 합니다.

그림: Pinball의 놀이판의 예시입니다. M = 2, N = 4. 공이 첫 번째 행(꼭대기)의 격자 (1, 2)에 등장합니다. 그 다음, 이 공은 (2, 2)로 움직인 후 1번 장치에 의하여 (2, 3)으로 이동할 것입니다. 이 공은 마침내 바닥의 격자 (4, 3)에 도착합니다.

놀이판의 크기와 장치들의 정보가 주어질 때, 공이 도달할 수 있는 바닥 격자가 단 하나 존재하도록 장치들을 설치하기 위한 최소 비용을 구하는 프로그램을 작성하세요.

#3624 upload 27 done 10 how_to_reg 10

핀볼 timer 1s memory 512MB

#3624

핀볼 1s 512MB