에너지를 유지하라

게임 회사가 새 게임기와 함께 내놓는 게임 Adventures of Captain Mikado를 만들고 있다. 이 게임에는 레벨이 $N$개 있고 $1$번부터 $N$번까지 번호가 붙어 있다. $i$번 레벨을 깨려면 에너지가 정확히 $E_i$만큼 든다. 즉 $i$번 레벨을 시작하는 시점의 에너지가 $E_i$ 이상이어야 하고, 레벨을 깨고 나면 에너지가 정확히 $E_i$만큼 줄어든다. 게임을 이기려면 $1$번 레벨부터 $N$번 레벨까지 번호 순서대로 모두 깨야 하고, 이미 깬 레벨로 되돌아갈 수 없다.

플레이어는 에너지 $0$으로 시작한다. 에너지는 레벨 곳곳에 흩어져 있는 상점 $M$개에서 에너지 팩을 사서 얻는다. 상점마다 강도가 $S$이고 가격이 $C$인 에너지 팩을 한 종류 판다. 플레이어는 지금 있는 레벨의 상점에서만, 그 레벨을 시작하기 전에 에너지 팩을 살 수 있다. 강도가 $S$인 팩을 사면 직전 에너지가 얼마였든 에너지가 곧바로 $S$가 된다.

레벨 $N$개를 모두 깨는 데 드는 게임 내 화폐의 최솟값을 구하라.

첫째 줄에 레벨 수 $N$과 상점 수 $M$이 주어진다 ($1 \le N, M \le 10^5$).

둘째 줄에 정수 $N$개 $E_1, E_2, \dots, E_N$이 주어진다. $E_i$는 $i$번 레벨을 깨는 데 드는 에너지이다 ($1 \le E_i \le 10^4$).

다음 $M$개 줄에는 상점 하나를 나타내는 정수 $L$, $S$, $C$가 주어진다. $L$은 상점이 있는 레벨 번호, $S$와 $C$는 그 상점이 파는 에너지 팩의 강도와 가격이다 ($1 \le L \le N$, $1 \le S \le 10^9$, $1 \le C \le 10^4$).

레벨 $N$개를 모두 깨는 데 필요한 게임 내 화폐의 최솟값을 한 줄에 출력한다. 모든 레벨을 깨는 것이 불가능하면 -1을 출력한다.