TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

86.2% (25/29)

Submission's AC Ratio

16.2% (31/191)

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

Sample Output 1

3

Sample Input 2

5 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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 5
1 1000 262144 65536 1 5
2 1000 262144 65536 1 5
3 1000 262144 65536 2 5
4 1000 262144 65536 2 5
5 1000 262144 65536 2 5
6 1000 262144 65536 2 5
7 1000 262144 65536 2 5
8 1000 262144 65536 3 4 5
9 1000 262144 65536 3 4 5
10 1000 262144 65536 3 4 5
11 1000 262144 65536 3 4 5
12 1000 262144 65536 3 4 5
13 1000 262144 65536 3 4 5
14 1000 262144 65536 3 4 5
15 1000 262144 65536 3 4 5
16 1000 262144 65536 3 4 5
17 1000 262144 65536 3 4 5
18 1000 262144 65536 4 5
19 1000 262144 65536 4 5
20 1000 262144 65536 4 5
21 1000 262144 65536 4 5
22 1000 262144 65536 4 5
23 1000 262144 65536 4 5
24 1000 262144 65536 4 5
25 1000 262144 65536 4 5
26 1000 262144 65536 4 5
27 1000 262144 65536 4 5
28 1000 262144 65536 4 5
29 1000 262144 65536 5
30 1000 262144 65536 5
31 1000 262144 65536 5
32 1000 262144 65536 5
33 1000 262144 65536 5
34 1000 262144 65536 5
35 1000 262144 65536 5
36 1000 262144 65536 5
37 1000 262144 65536 5
38 1000 262144 65536 5