Егор проходит отбор в студсовет ФКСиС. В студсовете состоит $$$n - 1$$$ человек. Егор условно пронумеровал их от $$$2$$$ до $$$n$$$. Председатель студсовета имеет номер $$$n$$$. Чтобы попасть в студсовет, Егор должен набрать как можно больше баллов. $$$i$$$-й студсоветчик начисляет Егору $$$a_i$$$ баллов за выполненное задание. А также некоторые из студсоветчиков могут направить Егора к коллегам, чтобы он продолжил выполнять задание у кого-нибудь из них. Так, если студсоветчик с номером $$$k$$$ может направить Егора к коллегам, он называет ему два числа: $$$l_k$$$ и $$$r_k$$$. Это означает, что Егор может выбрать любого студсоветчика с номером $$$q \in [l_k, r_k]$$$ и пойти к нему. Без направления Егор идти не может.
Себя Егор обозначил номером $$$1$$$.
Помогите Егору просчитать свои шансы. Посчитайте максимальное количество баллов, которое Егор может набрать. Если Егор не сможет добраться до председателя студсовета, выведите «No»(Без кавычек).
Первая строка содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \lt n \leq 10^5$$$) - количество студентов в студсовете (с учётом Егора) и количество студсоветчиков, которые могу отправить Егора дальше.
Вторая строка содержит числа $$$a_1, a_2, ... , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - баллы, которые может получить Егор у студсоветчиков. Обратите внимание, что у Егора уже есть $$$a[1]$$$ баллов на старте.
Следующие $$$m$$$ строк содержат 3 числа $$$k$$$, $$$l$$$, $$$r$$$ ($$$1 \leq k \lt l \leq r \leq n$$$) - описание студсоветчиков.
Выведите максимальное количество баллов, которое сможет набрать Егор, или «No» (без кавычек), если Егор не сможет добраться до председателя.
6 4 5 1 3 3 2 3 1 2 6 3 4 5 2 5 5 5 6 6
13
5 2 6 3 5 1 1 1 3 4 2 4 5
No
| BSUIR Open X. Reload. Semifinal |
|---|
| Закончено |
