11551번 - Keep it energized 다국어

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 E_i units of energy to be completed. This means that in order to complete that level, the user’s energy should be at least E_i, 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?

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 ≤ 10⁵). The second line contains N integers E₁, E₂, . . . , E_N, where E_i is the energy required to complete the i-th level (1 ≤ E_i ≤ 10⁴ 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 ≤ 10⁹ and 1 ≤ C ≤ 10⁴).

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.