P12006 【MX-X10-T2】[LSOT-4] NetEase Cloud Music

Don't underestimate my intelligence network. I know your annual music genre is anime, and your annual keywords are future, world, forever, right?

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`.

- 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 one line containing an integer—the total sum of quality values. If the sum cannot be uniquely determined, output the string `Impossible`.

**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