제리와 일

제리에게는 해야 할 일이 $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$가 주어진다 ($1 \le a, b \le n$; $a < b \le a + 10$). 일 $b$는 일 $a$가 끝난 뒤에만 할 수 있다는 뜻이다. 같은 쌍이 두 번 주어지지 않는다.

음이 아닌 정수 하나를 출력한다. 가능한 어떤 순서로 일을 하더라도 돈이 음수가 되지 않게 하려면, 제리가 처음에 가지고 있어야 하는 최소 금액이다.