2283 . 調分
TopCoder
Tags
Description
「你是鄭教授！」
「不，我是鄭笨蛋，你才是鄭教授。」
經過十多年的努力，你終於如願當上了鄭教授，現在你要給你的學生裝弱學導論的學期成績，有 $n$ 個學生，編號由 $1$ 到 $n$，而你覺得 $1$ 號學生太會裝弱了，因此你要給他最低的分數（裝弱學導論的分數是越低越好）。這個分數不一定要在 $0$ 到 $100$ 之間，可以是任意整數。但是你也不能隨便亂給分，你知道學期中班上的學生形成了 $m$ 個群組，每一群組裡的人都討論過一次作業，因此他們的學期成績不應該相差超過某個數值（也就是說，對於第 $i$ 個群組，分數最高和最低的人相差不能超過 $w_i$）。注意到，一個學生可能在多個群組，也可能不在任何群組內。
給定 $m$ 個群組的組成以及他們分數的最大差距，你想要知道 $1$ 號學生和分數最高的學生最多能差多少分。
Input Format
第一行輸入兩個整數 $n, m$，代表學生的個數和群組的數量。
接下來 $m$ 行，每一行會先有兩個數字 $k_i, w_i$，代表該群組的人數和成績的最大差距。接下來會有 $k_i$ 個整數 $x_1, \dots, x_{k_i}$，為該群組內學生的編號。保證一個群組內學生編號都相異。
對於所有測資，$2 \leq n \leq 2 \times 10 ^ 5, m \leq 2 \times 10 ^ 5,\ 0 \leq w_i \leq 10 ^ 9$
$ 2 \leq k_i \leq n, \sum_{i=1} ^ m k_i \leq 4 \times 10 ^ 5$
Output Format
輸出一個整數，為$1$ 號學生與最高分的學生差距最大值。如果差距可以是無窮大，輸出-1。
Sample Input 1
3 1
3 3 1 2 3
3 3 1 2 3
Sample Output 1
3
Sample Input 2
5 3
2 3 1 4
3 5 2 3 5
3 2 1 2 3
2 3 1 4
3 5 2 3 5
3 2 1 2 3
Sample Output 2
7
Sample Input 3
4 1
3 5 2 3 4
3 5 2 3 4
Sample Output 3
-1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 3~7 | $m = 1$ | 6 |
| 3 | 8~17 | $m = n - 1, \forall 1 \leq i \leq m, k_i = 2$ | 16 |
| 4 | 8~28 | $\forall 1 \leq i \leq m, k_i = 2$ | 20 |
| 5 | 0~38 | 無其他限制 | 58 |