28771번 - Джерри и задачи 다국어

У Джерри накопилось $n$ дел, которые ему нужно сделать. Пока он будет их выполнять, он будет зарабатывать или тратить деньги. А именно, для каждого дела он знает, сколько денег он получит или потратит в момент завершения этого дела. Также известно, что Джерри не будет выполнять несколько дел одновременно, и не будет прерываться во время выполнения никакого дела.

Однако, между делами есть зависимости. Некоторые дела можно выполнять только после того, как выполнены некоторые другие необходимые дела. Каждая зависимость описывается номерами двух дел $a$ и $b$, и обозначает, что дело номер $b$ может быть выполнено только после того, как было выполнено дело номер $a$. Так как Джерри довольно хорошо спланировал свои дела, для каждой зависимости верно что $a < b \le a + 10$.

Джерри --- ответственный, и не будет нарушать зависимости между делами. Тем не менее, он не знает точный порядок, в котором он будет выполнять дела, так как ему будет мешать Том.

Ему интересно, какое минимальное количество денег ему нужно иметь изначально, чтобы вне зависимости от того, в каком из возможных порядков он будет выполнять дела, ему гарантированно хватило денег (т.е. чтобы количество денег ни в какой момент времени не стало отрицательным).

В первой строке даны два целых числа $n$ и $m$ --- количество дел, которые нужно сделать Джерри, и количество зависимостей между ними ($1 \le n \le 100\,000$, $1 \le m \le {10}^6$). В следующей строке дано $n$ целых чисел $c_i$, $i$-е из них равно величине, на которую изменится количество денег у Джерри после выполнения $i$-о дела ($-{10}^9 \le c_i \le {10}^9$).

В следующих $m$ строках дано описание зависимостей между делами. Каждая зависимость описывается парой чисел $a$ и $b$, обозначающей что дело номер $b$ можно выполнять только если уже выполнено дело номер $a$ ($1 \le a, b \le n$; $a < b \le a + 10$). Гарантируется, что никакая пара не встречается дважды.

Выведите одно целое неотрицательное число --- минимальное количество денег, которое Джерри должен иметь изначально, чтобы вне зависимости от порядка выполнения дел, количество денег никогда не становилось отрицательным.