Description

In 2077, NetEase Cloud Music introduced a statistical feature. Each song has a "quality value" (any integer), and the "combined value" of any two consecutively listened songs is the sum of their quality values.

In 2077, Little H listened to $n$ songs, but he does not know the quality values of each song. You are given the combined values $S_i$ for $1 \le i < n$, where $S_i$ corresponds to the $i$-th and $(i+1)$-th songs. Now, Little H wants to change his listening method: he will listen to songs $m$ times, and in the $i$-th listening session, he will listen to the $a_i$-th song $b_i$ times.

Little H asks you to calculate the total sum of the quality values of all songs listened to in the new method. A song listened to multiple times contributes its value multiple times. However, if it is impossible to determine the total sum uniquely, output Impossible.

Input Format

• The first line contains two integers $n$ and $m$, representing the number of songs and listening sessions.
• The second line contains $n-1$ integers $S_1, S_2, \ldots, S_{n-1}$.
• The next $m$ lines each contain two integers $a_i$ and $b_i$, describing the $i$-th listening session.

Output Format

Output one line containing an integer—the total sum of quality values. If the sum cannot be uniquely determined, output the string Impossible.

5 2
8 6 7 2
2 2
3 2

12

5 2
8 6 7 2
2 2
3 10

Impossible

20 19
425 46 176 409 156 35 128 467 534 411 362 760 32 17 403 210 462 10 94
15 104
12 193
6 249
18 845
1 72
15 269
2 633
10 858
14 282
14 950
5 98
11 162
12 296
14 846
15 793
11 858
19 942
1 886
19 968

283895

Hint

Sample Explanation #1

The second and third songs were each listened to twice. Since their combined value is $6$, the total contribution is $2 \times 6 = 12$ (using the distributive property).

Sample Explanation #2

The total sum equals $12$ plus the third song's quality value multiplied by $8$. However, the third song's quality value cannot be determined from the given information, so the output is Impossible.

Data Range

• For $10\%$ of the data: $m = 1$.
• For another $30\%$: $m = 2$.
• For all data: $2 \le n \le 10^5$, $1 \le m \le 10^5$, $1 \le S_i, b_i \le 1000$, $1 \le a_i \le n$.

Translation by DeepSeek R1