952 . 糖果分配
TopCoder
.jpg)
Tags
Description
今天是 YTP 魔法學院的新生開學日，身為校長的小 P 決定要發糖果鼓勵新生們。
已知這次的新生總共有 $n$ 個人，小 P 會先依序發給第 $1,2,\dots,n$ 個人每人一顆糖果，再依序發給第 $n,n-1,\dots,1$ 個人每人一顆糖果，再依序發給第 $1,2,\dots,n$ 個人每人一顆糖果……如此不斷重複，但發到某個時候，小 P 有點搞糊塗了，突然忘記自己發了多少糖果，僅知道某 $m$ 位新生目前已經拿了多少糖果，請你設計一個程式計算在僅有的線索下小 P 「至少」已經發了多少糖果，如果線索不合理則輸出 Impossible。
Input Format
第一行輸入依序輸入兩個正整數 $n,m$。
接下來依序輸入 $m$ 行，每行包含兩個正整數 $x,c$，表示目前第 $x$ 位學生已經拿到了 $c$ 顆糖果。
- $1 \le n \le 2 \times 10^ 9$。
- $1 \le m \le \min(n, 10^ 5)$。
- $1 \le x \le n$。
- $1 \le c \le 2 \times 10^ 9$。
- 保證所有 $x$ 皆不一致。
Output Format
如果線索不合理則輸出 "Impossible" (不含雙引號)，否則輸出一個整數表示目前小 P「至少」已經發了多少糖果。
Sample Input 1
5 3 1 3 2 3 3 3
Sample Output 1
13
Sample Input 2
5 2 4 2 3 3
Sample Output 2
13
Sample Input 3
5 2 1 4 3 3
Sample Output 3
Impossible
Hints
在範例 1 中，如果小 P 發了 13 顆糖果，他會依序發給
$$1,2,3,4,5,5,4,3,2,1,1,2,3$$
因此五個學生分別得到了 $3,3,3,2,2$ 顆糖果。
Problem Source
YTP 2025 高中組程式挑戰營 p2
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測試資料 | 0 |
| 2 | 0~20 | 無額外限制 | 10 |