该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小赵有$\red{n}$道题,但他不知道出不出

已知有$\red{m}$个算法,一场比赛一定每种算法都有且只有一个,所以他可以出$\red{k}$场比赛(这里注意,比赛不能有重题,即两场比赛不能有相同的题,不然参加了前一场的人就有利了),且有些题必须要搭配使用,有$\red{p}$种方案

输入格式

先输入$m,p$

接下来$m$个数$a_1,a_2...a_m$,表示第$i$种算法题目个数,这里$1$到$a_1$道题是第1种算法,$a_1+1$到$a_1+a_2$道题是第2种算法,以此类推...

接下来$p$行

每行2个数$x,y$,表示第$x$题和第$y$题必须放在一起(若没有搭配的两种相邻算法题,就不能放在一起)

保证$x,y$是相邻的两种算法

输出格式

一个数$k$

样例

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

2

解释

数据范围

$1 \le m \le 100$

$1 \le p \le 10^5$

$1 \le a_i \le 100$

$1 \le x,y \le n$

注意

本题数据是在 Windows 环境下生成的，所有的换行符都是 \r\n 而不是 \n。