내 것은 내 것

새로 출시된 인기 비디오 게임 "Mining Simulator"가 있다. 이 게임에서는 특정 시각에 희토류 광물이 나타나고, 나타난 광물을 채굴할 수 있다. 채굴한 광물은 나중에 돈으로 바꿀 수 있다. 한 번 나타난 광물의 양은 나타나 있는 시간에 비례하며, 각 광물의 단위당 가격은 미리 정해져 있다.

이 게임에는 하루 동안 광물이 나타나는 시각을 알려 주는 지질 센서가 있고, 각 날의 시작에 광물별 가격표가 주어진다. 광물이 나타나 있는 시간만큼 정확히 채굴한다고 가정할 때, 광물을 일부만 채굴할 수는 없다. 즉, 어떤 광물이 나타난 것을 보면 아예 채굴하지 않거나 전부 채굴해야 한다. 또한 한 번에 하나의 광물만 채굴할 수 있다.

하루 동안 나타나는 m가지 광물의 가격과 n개의 광물 출현 목록이 주어질 때, 그날 채굴로 벌 수 있는 최대 금액을 출력하는 프로그램을 작성하라. 광물의 양은 출현 시간(끝 시각 - 시작 시각)이다. 앞선 채굴을 마친 직후에 다음 광물을 채굴할 수 있다. 다시 말해, 어떤 채굴의 끝 시각은 다른 채굴의 시작 시각과 같을 수 있다. 그림 L.1의 경우, 시각 2에 나타나 시각 5에 사라지는 1번 광물을 선택하면 광물의 양은 5 - 2 = 3이고 3 × 2 = 6을 번다. 이어서 시각 7에 나타나 시각 11에 사라지는 2번 광물을 선택하면 광물의 양은 11 - 7 = 4이고 4 × 3 = 12를 번다. 따라서 합계 18을 번다.

그림 L.1: 채굴 예시. 각 광물 (s, e, t)에서 s는 시작 시각, e는 끝 시각, t는 광물의 종류다. 따라서 광물의 양은 e - s이고 얻을 수 있는 수익은 (e - s) × t의 가격이다.

프로그램은 표준 입력에서 입력을 읽는다. 입력은 두 정수 m과 n (1 ≤ m ≤ 100, 1 ≤ n ≤ 10,000)이 있는 한 줄로 시작한다. 여기서 m은 광물의 종류 수, n은 하루 동안의 광물 출현 횟수다. 광물의 종류는 1부터 m까지 번호가 붙는다. 다음 m개 줄에는 그날 i번째 광물 종류의 단위당 가격이 정수 하나로 주어진다(가격은 1과 10,000 사이). 다음 n개 줄은 광물 출현을 나타낸다. 각 줄에는 세 정수 s, e, t가 주어지며, s는 시작 시각, e는 끝 시각, t는 광물의 종류다. 각 광물 출현에 대해 0 < s < e < 15,000이고 1 ≤ t ≤ m이다. 각 출현에서 광물의 양은 e - s이다.

프로그램은 표준 출력에 출력한다. 정확히 한 줄을 출력한다. 그 줄에는 그날 벌 수 있는 최대 금액이 있어야 한다.