페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4395

채굴 시뮬레이터 1s 512MB

문제

최근 인기 있는 새로운 비디오 게임 “채굴 시뮬레이터(Mining Simulator)”가 출시되었다.

게임 내에서는 특정 시간에 광석이 나타나며, 나타날 때마다 채굴할 수 있다. 채굴 후에는 광석을 돈으로 바꿀 수 있다. 출현 시 얻을 수 있는 광석의 양은 출현 기간에 비례하며, 각 광석의 kg당 가격은 사전에 공지된다.

이 게임에는 각 광석의 kg당 가격표가 표시는데, 광석을 부분적으로는 채굴할 수 없으며(주어진 항목 중 하나도 채굴하지 않거나 모두 채굴해야 함) 한 번에 하나의 광석만 채굴할 수 있다.

m개 광석의 가격과 n개 광석의 출현 정보가 주어지면, 채굴로 얻을 수 있는 최대 금액을 출력하는 프로그램을 작성하시오.

광석의 양은 출현 시간(종료 시간 – 시작 시간)이다. 예를 들어 광석이 2시에 출현하기 시작하여 5시에 출현이 끝난다면 총 (5-2 = 3) kg만큼의 광석을 채굴 할 수 있다.

또한 이전 채굴을 마친 후 바로 광석을 채굴할 수 있기에 하나의 광석 채굴 종료 시간은 다른 광석 채굴 시작 시간과 동일할 수 있다.

아래 그림 L.1에 묘사된 예시를 보면, 2시에 나타나고 5시에 사라지는 유형 1의 광석을 채굴하면 광석의 양은 5 − 2 = 3 kg이고 3 × 2 = 6 원을 얻는다. 다음으로, 7시에 나타났다가 11시에 사라지는 유형 2의 광석을 채굴했다면 11 − 7 = 4 kg을 채굴하여 4 × 3 = 12 원을 얻는다. 따라서 총 18 원을 얻을 수 있다. 

그림 L.1: 각 광석(s , e , t) 에 대해 s는 시작 시간, e 는 종료 시간, t 는 광석 유형이다. 따라서 광석량은 (e - s) kg이고, 얻을 수 있는 수입은 ( e - s ) × t 원이다. 


입력

첫 줄에 광석 유형의 수 m 과 발생하는 광석의 수 n이 주어진다 (1 ≤ m ≤ 100, 1 ≤ n ≤ 10\,000). 광석 종류는 1부터 m까지 있다.

다음 m줄에는 i 번째 광석 유형의 kg당 가격이 주어진다. (가격은 1원에서 10\,000원 사이의 값이다).

다음 n줄에는 광석 발생 정보가 세 개의 정수 s , e , t로 주어진다. 여기서 s 는 시작 시간, e 는 종료 시간, t는 각 광석 유형이며 각 발생 시 광석의 양은 e-s이다. (0 < s < e < 15,000, 1 ≤ t ≤ m)


출력

채굴을 통해 얻을 수 있는 최대 금액을 출력한다.


예제 #1

2 5

2

3

2 5 1

4 5 2

4 6 1

7 11 2

6 10 1
18

예제 #2

3 5

2

3

1

1 4 1

3 6 3

5 8 2

7 10 1

9 12 2
24

예제 #3

5 7

1

2

3

4

5

1 5 2

3 8 1

2 4 3

3 9 2

4 10 5

7 11 4

5 7 3
36

출처

ICPC 2019 Asia Regional – Seoul Problem L

로그인해야 코드를 작성할 수 있어요.