H. Holiday Regifting
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a town there live $$$n$$$ people. Each person has some capacity $$$c_i$$$ for how many gifts they can store in their house.

There also exist $$$m$$$ friendships in the town. Each friendship has a 'mentor' corresponding to the friend in the friendship with the higher index.

Initially, no member of the town has any gifts. Every day, Santa comes to town and tasks an elf with giving a single gift to the member of the town with index $$$1$$$. Unfortunately, this elf has a lot of work ahead of them.

If the elf gives a present to a town member whose house will not be filled by the present, they will accept it. However, if the town member's house would be completely filled by the present they will throw out all of their gifts (emptying their house) and tell the elf to deliver one gift to each of that town member's mentors, in increasing order of index. Any remaining leftover gifts will be thrown in the town incinerator.

The elf wonders what it will do if a town member has more mentors than gifts to give, but luckily all town members have at least as much capacity in their house as the number of mentors they have.

However, there is some additional complexity regarding how the elf gives out gifts. While the elf is in the middle of completing a gift-giving order, they can try to deliver a gift to a different nearly full house, causing a nested request. In this case, the elf will always deliver gifts corresponding to the most recent request (keeping track of a 'call stack' of requests to be carried out). It can be shown that the elf's actions throughout the day will be completed in a finite number of operations.

Santa, noticing the town's gift-giving shenanigans, is worried that on Christmas Day there will be no remaining gifts in the town, as they will all have been thrown in the incinerator. He has tasked you with finding the first day on which there are no gifts remaining in any house in the town. If this day will never come, output $$$-1$$$ instead.

In the positive case, as the answer may be large, compute the first such day modulo 998244353.

Note: throughout the gift-giving exercise, no house will ever be at full capacity for gifts. Any person will throw out gifts exactly when they would reach capacity when given the incoming gift.

Input

The first line of input contains two integers $$$n, m$$$ ($$$1 \leq n \leq 10^4$$$, $$$0 \leq m \leq 3 \cdot 10^4$$$) — the number of people in the town and the number of friendships in the town respectively.

The second line of input contains $$$c_1, c_2, \dots, c_n$$$ ($$$2 \leq c_i \leq 10^5$$$) — the capacity of each person's house.

The following $$$m$$$ lines of input contain two integers $$$u_i, v_i$$$ ($$$1 \leq u_i \lt v_i \leq n$$$) — the people in the $$$i$$$-th friendship. It is guaranteed that all listed friendships will be distinct.

Output

Output the first time when all houses in the town contain zero gifts. As the time may be large, output its value modulo 998244353. If no such time exists, output $$$-1$$$.

Examples
Input
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
Output
24
Input
3 0
95 13 77
Output
95
Input
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
Output
8739360