uCoder | 1217 | Nível: 6 | Tempo Limite: 4
Keep it energized
Adaptado por Erich Rodrigues
Competição: SBC - ACM/ICPC - Maratona de Programação de 2015 - Final Nacional
The Incredible Consoles Production Company (ICPC) is now designing its newest video game console model, the Super-Arcade Reloaded (SAR). The launch of the SAR will be accompanied by the release of a flagship game, which will only be available to its users. This game, which incidentally shall be called Adventures of Captain Mikado (ACM), even features an in-game currency which can be conveniently bought using real-world money!
The ACM is a very simple game consisting of N levels numbered 1, 2, . . . , N , the i-th level requiring exactly Ei units of energy to be completed. This means that in order to complete that level, the user’s energy should be at least Ei , and after doing so it will decrease in exactly that amount. To win the game the user should complete all the levels in increasing order, starting at level 1 and continuing until level N without ever going back to some already-completed level.
Initially the user starts with no energy, and in order to get some he must buy energy packs from the in-game shops distributed among the N levels. There are M such shops. Each shop sells an energy pack having a strength S and a cost C that depend on the shop. The user can only buy energy packs from the shops in the level he is currently in, before starting to complete that level. The effect of buying an energy pack of strength S is that the user’s energy immediately turns into S, regardless of which value it had before.
In order to increase even further its sales, the ICPC has thought of a revolutionary promotion: it will reimburse the full cost of the SAR to whoever completes the ACM game using the minimum amount of in-game cash. Given the description of the game, can you help them find out what is the minimum amount of in-game cash required to finish the game?
Entrada
The first line contains two integers N and M , representing respectively the number of levels and the number of shops in the game (1 ≤ N, M ≤ 105 ). The second line contains N integers E1 , E2 , . . . , EN , where Ei is the energy required to complete the i-th level (1 ≤ Ei ≤ 104 for i = 1, 2, . . . , N ). Each of the next M lines describes a shop with three integers L, S and C, representing respectively the level where the shop is located, and the strength and cost of the energy pack it sells (1 ≤ L ≤ N , 1 ≤ S ≤ 109 and 1 ≤ C ≤ 104 ).
Saída
Output a line with an integer representing the minimum amount of in-game cash that is required to complete all N levels in the game. If it is impossible to complete all the levels, write the value −1.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
3 4 |
-1 |
|
5 4 |
14 |