样例输入

3

11 4 13

19 10

8 7

11 4

26 1

84 2

15 4

19 4

1 9

4 6

19 5

15 10

2 1

3 100

4 10000

5 1000000

11 4 13

19 10

8 7

11 4

26 1

4 2

15 4

19 4

1 9

4 6

19 5

15 10

2 1

3 2

4 3

5 4

1 1 1000000000

0 500000000

1 1

样例输出

206

5

impossible