Othmar 小姐是一位小学老师，她在科学课上使用了一本非常有趣的教科书。书中的所有章节内容最多只依赖于前一章的内容，同时有几个章节被标记为“总结性概念”章节，这些章节没有任何后续章节依赖于它们——它们基本上代表了在阅读它们之前必须阅读的所有先前章节内容的总结。非“总结性概念”的章节被称为“先修章节”。

由于疫情导致的各种延误，Othmar 小姐的教学进度远远落后于计划。现在尝试讲完书中所有的“总结性概念”章节（以及它们所需的先修章节）已经太晚了，所以她决定只再讲两个“总结性概念”章节。为了让孩子们轻松一点，她决定选择两个需要阅读量最少的“总结性概念”章节——这不仅包括这些章节本身，还包括它们的所有先修章节。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，其中 $n$ ($2 \le n \le 1000$) 表示章节总数（编号为 $1$ 到 $n$），$m$ ($0 \le m < n$) 表示章节依赖关系的个数。接下来是 $n$ 个正整数，表示每一章的页数。这些数值可能分布在一行或多行中，且任何一章的页数均 $\le 1000$。随后是 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示必须先阅读第 $a$ 章才能阅读第 $b$ 章。在这些行中，没有任何章节作为第二个整数出现超过一次。题目保证至少有两个“总结性概念”章节。

输出格式

输出为了完成两个“总结性概念”章节所需要阅读的最少页数。

样例

样例输入 1

7 6
10 9 6 4 2 10 12
1 2
1 3
2 4
2 5
3 6
3 7

样例输出 1

25

样例输入 2

4 2
10 7 4 6
1 4
2 3

样例输出 2

27