uva11518測資A

Input:
19
3 2 1
1 2
2 3
2
16 7 2
11 16
4 13
5 9
10 5
11 10
5 7
10 5
16
10
17 4 4
9 15
5 13
10 8
3 14
15
9
15
16
971 16 5
66 918
918 321
396 851
577 174
954 437
161 129
504 740
600 624
859 325
504 45
218 654
386 379
733 257
451 918
318 506
749 117
489
412
779
16
922
834 26 2
103 62
544 182
782 393
546 469
380 47
132 267
396 389
93 527
417 627
136 369
71 373
332 60
576 789
323 803
36 531
20 103
257 592
541 116
697 731
177 317
624 87
502 29
479 122
498 834
115 114
818 752
485
769
930 45 4
477 381
521 179
829 59
552 706
127 633
476 797
406 242
281 280
195 525
330 462
75 874
92 608
473 115
338 894
263 761
227 733
314 130
674 98
594 890
676 424
6 571
53 439
593 429
876 313
414 105
211 12
372 467
382 487
250 533
830 475
846 179
729 851
555 678
679 620
883 299
224 282
820 605
30 586
275 869
838 705
161 720
311 68
789 261
632 66
119 734
830
733
930
22
548 24 5
518 466
247 276
121 336
255 521
314 296
269 12
30 291
525 263
64 303
39 231
126 349
409 207
337 420
342 469
281 86
168 362
207 209
216 139
229 478
228 547
244 264
38 207
131 502
538 524
141
82
428
21
8
921 24 3
351 871
778 71
195 844
596 391
837 617
775 821
880 199
508 514
23 90
241 224
720 651
399 83
363 45
179 192
871 844
649 429
664 333
46 626
910 709
433 699
786 205
582 743
352 482
741 49
230
909
885
733 14 2
500 415
31 719
490 245
626 302
385 221
330 730
511 438
453 144
725 66
437 370
668 357
574 324
109 256
46 89
5
494
490 26 6
218 333
359 214
181 401
281 447
274 23
273 9
50 161
466 130
429 247
425 63
320 67
297 357
371 203
183 356
474 6
141 129
247 329
65 192
111 331
141 349
132 263
11 390
101 119
78 188
66 134
206 324
342
193
114
245
105
398
276 27 8
36 229
172 53
193 89
219 195
221 61
15 26
125 262
24 184
8 146
78 145
31 87
260 109
255 3
47 233
268 15
144 148
58 237
216 126
124 151
233 127
253 101
70 104
237 161
270 109
235 21
46 172
203 87
22
94
99
42
57
83
145
257
432 13 3
121 301
92 265
344 425
261 357
165 245
345 148
234 130
111 311
327 287
188 26
408 244
22 420
322 352
107
71
349
736 49 5
661 455
727 545
440 77
388 723
52 276
411 160
248 721
602 648
465 238
173 587
59 722
475 94
416 53
618 667
120 285
574 378
183 457
276 566
634 569
142 416
174 569
292 613
695 645
510 677
403 676
721 623
122 541
649 275
415 61
56 144
381 331
386 174
608 623
163 553
103 344
608 693
105 92
61 460
647 231
699 100
93 318
252 273
284 40
101 639
41 253
647 382
96 734
728 485
371 71
185
339
703
43
498
568 28 1
441 313
353 209
418 447
35 240
245 81
358 560
370 535
125 384
130 322
554 120
103 411
271 254
486 465
242 317
414 321
310 383
20 47
62 467
46 181
394 46
468 193
337 288
38 337
556 512
1 470
459 559
516 438
38 10
315
54 40 10
15 41
32 40
14 19
25 28
40 2
40 28
36 32
24 48
43 18
26 1
32 7
25 12
22 3
16 37
43 15
41 12
26 50
4 28
15 53
19 36
47 51
37 48
33 34
26 4
39 23
43 45
22 48
51 38
41 11
17 53
25 39
13 24
53 54
36 49
25 33
40 3
11 22
44 42
32 13
46 16
44
22
44
32
28
11
38
5
8
4
720 7 2
205 5
486 710
604 449
435 290
72 601
255 520
603 348
596
613
240 38 5
140 57
190 195
222 167
29 175
5 173
126 190
162 74
99 21
184 47
214 159
100 165
172 239
205 23
139 213
224 162
127 111
192 153
175 170
21 50
75 124
39 120
170 18
124 22
187 152
157 14
229 152
43 24
183 88
204 185
58 119
56 231
69 137
169 67
25 197
168 118
95 82
31 91
55 170
65
165
179
217
224
626 25 8
91 324
420 233
226 570
526 447
304 500
318 47
402 319
146 511
123 237
178 464
103 612
297 276
235 325
114 489
515 109
356 352
168 2
536 111
548 537
235 22
582 276
129 491
270 414
145 68
385 432
399
605
233
27
321
335
6
285
303 2 7
74 299
159 64
89
159
26
107
181
218
270
Output:
2
5
3
5
2
5
5
3
2
6
8
3
5
1
17
2
7
8
8