#P18613. Holiday Regifting

Holiday Regifting

Holiday Regifting

镇上住着 n 个人,第 i 个人的房屋最多能容纳 c_i 件礼物。镇上还有 m 对朋友。每对朋友中,编号较大的人是编号较小的人的“导师”。

最初,所有人的房屋里都没有礼物。每天,圣诞老人派一位精灵给编号为 1 的人送一件礼物。精灵递送礼物时,遵循以下规则:

  • 如果接收者放入这件礼物后,房屋仍没有装满,他就收下这件礼物。
  • 如果放入这件礼物恰好会装满房屋,他立即把屋内的全部礼物拿出来,使房屋变空,并要求精灵按导师编号从小到大的顺序,给他的每位导师各送一件礼物。剩余礼物全部丢进焚烧炉。

保证每个人的房屋容量,至少等于他的导师数量,所以需要转送的礼物总是够用。

递送途中也可能遇到另一个即将装满房屋的人,从而产生新的递送任务。此时精灵先完成最新产生的任务,再继续此前尚未完成的任务,也就是按调用栈的方式处理。可以证明,每一天的所有递送任务都会在有限步内完成。

圣诞老人担心,某一天结束时,镇上所有房屋都没有礼物,所有礼物都已经被焚烧。请找出第一次出现这种情况的是第几天。若永远不会出现,输出 -1;否则输出这个天数模 998244353 的值。

注意:房屋中的礼物数永远严格小于其容量;正好达到容量时就会立即清空。所求状态是在当天全部递送任务完成之后。

输入格式

第一行两个整数 n、m,分别表示人数和朋友对数。

第二行 n 个整数 c_1,c_2,...,c_n,表示各人的房屋容量。

接下来 m 行,每行两个整数 u_i、v_i,表示一对朋友,满足 u_i<v_i,所以 v_i 是 u_i 的导师。保证所有朋友对互不相同,输入这些朋友对的顺序不作保证。

数据范围:1≤n≤10000,0≤m≤30000,2≤c_i≤100000,1≤u_i<v_i≤n。保证 c_i 不小于编号 i 的人的导师数量。没有连通性保证。

输出格式

若不存在这样的天数,输出 -1;否则输出第一次所有房屋都为空的天数模 998244353 的值。

样例输入 1

5 10
4 3 2 2 2
1 3
3 4
1 4
1 5
2 5
2 4
1 2
2 3
3 5
4 5

样例输出 1

24

样例输入 2

3 0
95 13 77

样例输出 2

95

样例输入 3

12 14
6 7 17 16 20 14 17 16 6 11 6 14
4 11
3 5
2 5
9 11
7 12
1 3
5 9
3 7
3 8
4 9
1 9
4 7
2 11
1 12

样例输出 3

8739360