밀물과 썰물 (큰 입력)

시간 제한5초메모리 제한512 MB

요약

밀물이 초당 10cm씩 빠지는 동굴 격자에서 천장·바닥 높이별 이동 가능 시점과 이동 시간을 따져 남서쪽 출구까지 가장 빨리 도착하는 시간을 구합니다.

난이도: 어려움10점 중 8점
유형: 최단 경로, 이분 탐색, 그래프, 힙
정답자: 아직 제출이 없습니다

문제

지하 동굴 수로를 카약으로 지나던 중 밀물이 들어와 갇혔다. 다행히 동굴 지도는 가지고 있다. 썰물이 시작되기 전에는 밖으로 나갈 수 없으니 한동안 여기서 기다려야 한다. 그동안 물이 빠지기 시작한 뒤 출구까지 가장 빨리 가는 방법을 계산해 두려고 한다.

동굴은 $N$ 행 $M$ 열 격자다. 지도는 같은 크기의 격자 두 장으로 이루어지고, 한 장은 각 칸의 천장 높이를, 다른 한 장은 각 칸의 바닥 높이를 센티미터 단위로 적어 놓았다. 동굴 바닥은 물이 빠져나가는 재질이라 수위가 내려가면 수위보다 높은 곳에는 물이 남지 않는다.

출발 지점은 지도의 북서쪽 끝 칸이다. 현재 수위는 $H$ 센티미터이고, 물이 빠지기 시작하면 초당 10센티미터씩 일정하게 내려가 0이 된다. 출구는 남동쪽 끝 칸에 있다. 지금은 물에 잠겨 있지만 물이 빠지기 시작하는 순간부터 지나갈 수 있다.

어느 시점에서든 북, 남, 동, 서로 인접한 칸으로 이동한다. 이동은 다음 조건을 모두 만족해야 한다.

수위와 현재 칸의 바닥 높이와 이동할 칸의 바닥 높이가 모두 이동할 칸의 천장 높이보다 50센티미터 이상 낮아야 한다. 따라서 바닥과 천장 사이가 50센티미터 미만인 칸에는 어느 방향에서도 들어가지 못한다.
이동할 칸의 바닥 높이는 현재 칸의 천장 높이보다도 50센티미터 이상 낮아야 한다.
지도 밖으로는 나가지 못한다.

카약을 타고 높이는 얼마든지 오르내릴 수 있다. 예를 들어 위 조건만 만족하면 바닥 높이가 10센티미터인 칸에서 바닥 높이가 9000센티미터인 인접한 칸으로 갈 수 있다.

조건을 그림으로 나타내면 다음과 같다.

첫 번째 그림에서는 수위와 오른쪽 칸의 천장 높이 차이가 50센티미터에 못 미쳐서 오른쪽으로 가지 못한다.
두 번째 그림에서는 현재 칸의 바닥 높이와 오른쪽 칸의 천장 높이 차이가 50센티미터에 못 미쳐서 오른쪽으로 가지 못한다.
세 번째 그림에서는 오른쪽 칸의 바닥 높이와 그 칸 자신의 천장 높이 차이가 50센티미터에 못 미친다. 이 칸에는 어느 방향에서도 들어가지 못한다.
네 번째 그림에서는 오른쪽 칸의 바닥 높이와 현재 칸의 천장 높이 차이가 50센티미터에 못 미쳐서 오른쪽으로 가지 못한다.

한 칸에서 다른 칸으로 이동을 시작하는 순간에 떠나는 칸에 물이 20센티미터 이상 남아 있으면 카약을 탈 수 있어서 이동에 1초가 걸린다. 그렇지 않으면 카약을 끌어야 해서 10초가 걸린다. 걸리는 시간은 떠나는 칸의 물 높이로만 정해지고 도착하는 칸과는 무관하다.

썰물이 시작되기까지는 시간이 많이 남아서, 물이 빠지기 전에는 원하는 만큼 움직여도 된다. 중요한 것은 물이 빠지기 시작한 순간부터 출구에 닿을 때까지 걸리는 시간이다. 이 시간을 구하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $H$ , $N$ , $M$ 이 주어진다. $H$ 는 처음 수위이고 단위는 센티미터이며, $N$ 과 $M$ 은 지도의 크기다. 그 뒤 $2N$ 개의 줄에 천장 높이와 바닥 높이가 다음 순서로 주어진다.

다음 $N$ 개의 줄에는 각각 $M$ 개의 정수가 공백으로 구분되어 주어진다. $i$ 번째 줄의 $j$ 번째 정수는 격자 위치 $(j, i)$ 의 천장 높이 $C_{ij}$ 이고 단위는 센티미터다. $i$ 가 커지는 방향이 남쪽, $j$ 가 커지는 방향이 동쪽이다.
그다음 $N$ 개의 줄에는 같은 형식으로 바닥 높이 $F_{ij}$ 가 주어진다.

출발 칸은 천장과 처음 수위 사이가 항상 50센티미터 이상이고, 천장과 바닥 사이도 항상 50센티미터 이상이다. 출구 칸은 천장과 바닥 사이가 항상 50센티미터 이상이다. 빠져나갈 길은 항상 존재한다.

제한

$1 \le T \le 50$
$1 \le N, M \le 100$
$1 \le H \le 10000$
$1 \le F_{ij} \le C_{ij} \le 10000$

출력

각 테스트 케이스마다 Case #x: t 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $t$ 는 물이 빠지기 시작한 순간부터 동굴을 빠져나올 때까지 걸리는 시간이며 단위는 초다.

모든 사건은 0.1초의 정수배인 시각에만 일어나므로 답은 항상 0.1의 배수다. $t$ 는 소수점 아래 한 자리까지 출력하고, 값이 정수여도 소수점 아래 한 자리를 반드시 붙인다.

노트

물이 빠지기 전에 동굴을 모두 지나갈 수도 있다. 이때는 출구에서 물이 빠지기 시작하기를 기다리면 되므로 답은 0이다. 예제 입력의 네 번째 테스트 케이스가 이 경우다.

예제 입력의 첫 번째 테스트 케이스에서는 처음에 수위와 동쪽 칸 천장 사이가 33센티미터뿐이다. 그래서 물이 빠지기 시작한 뒤 1.7초를 기다려야 그 칸에 들어갈 수 있다. 들어갈 수 있게 된 시점에는 서쪽 칸의 물이 바닥에서 3센티미터 높이까지 내려가 있으므로, 출구까지 카약을 10초 동안 끌어야 한다.

두 번째 테스트 케이스는 상황이 낫다. 인접한 칸의 천장이 충분히 높아서 물이 빠지기 전에 $(1, 1)$ 까지 갈 수 있다. 거기서 수위가 90센티미터로 내려갈 때까지 1초를 기다린 다음 남쪽으로, 이어서 동쪽으로 카약을 저으면 빠져나온다. 모두 3초가 걸린다. $(2, 1)$ 은 천장이 높은데도 지나가지 못한다. 그 칸으로 들어갈 수 있는 칸인 $(1, 1)$ 과 $(2, 0)$ 의 천장과 그 칸 바닥 사이가 각각 10센티미터뿐이기 때문이다.

세 번째 테스트 케이스는 첫 번째와 비슷하다. 수위가 50센티미터로 내려갈 때까지 출발 칸에서 기다려야 한다. 그 뒤로는 출구를 향해 카약을 저을 수 있지만, 세 번 움직여 3초가 지나면 수위가 20센티미터, 즉 바닥보다 10센티미터 높은 상태가 되어 네 번째 이동은 카약을 끌게 된다.

예제8

예제 1

입력

4
200 1 2
250 233
180 100
100 3 3
500 500 500
500 500 600
500 140 1000
10 10 10
10 10 490
10 10 10
100 3 3
500 100 500
100 100 500
500 500 500
10 10 10
10 10 10
10 10 10
100 2 2
1000 1000
1000 1000
100 900
900 100

예상 출력

Case #1: 11.7
Case #2: 3.0
Case #3: 18.0
Case #4: 0.0

예제 2

입력

1
100 5 5
1000 1000 100 1000 1000
1000 1000 100 1000 1000
1000 1000 100 1000 1000
1000 1000 100 1000 1000
1000 90 1000 1000 1000
10 10 99 10 10
10 10 99 10 10
10 10 99 10 10
10 10 99 10 10
10 10 10 10 10

예상 출력

Case #1: 28.0

예제 3

입력

1
100 5 5
1000 140 1000 1000 1000
100 60 60 60 1000
1000 60 60 60 1000
1000 60 60 60 1000
1000 1000 1000 1000 1000
10 10 10 10 10
10 59 59 59 10
10 59 59 59 10
10 59 59 59 10
10 10 10 10 10

예상 출력

Case #1: 18.0

예제 4

입력

12
98 7 5
180 210 243 240 88
215 666 119 118 181
641 65 371 493 107
123 257 575 88 98
412 90 292 78 618
100 96 348 170 483
568 39 166 237 190
15 41 52 35 9
28 73 41 28 64
51 59 19 34 18
32 72 69 34 75
55 75 52 47 29
18 66 64 12 7
15 20 21 55 77
169 5 7
324 160 317 67 550 308 214
69 206 90 100 391 117 101
133 239 194 202 216 217 146
518 191 383 526 168 126 348
197 302 36 100 269 200 236
4 53 42 52 38 71 17
25 54 49 23 79 73 39
52 71 1 39 37 27 56
75 78 42 60 57 57 28
66 61 22 11 37 66 80
189 8 8
379 268 487 206 39 613 49 305
183 215 170 122 353 112 109 524
433 207 45 207 298 194 189 482
50 418 256 442 169 188 317 169
40 202 194 353 164 381 154 231
285 54 170 217 98 63 148 252
224 169 542 169 184 53 52 619
108 36 204 500 101 354 91 206
9 74 49 62 1 46 39 50
54 69 70 78 29 63 29 35
56 63 4 50 44 52 22 60
17 80 69 4 51 76 73 4
11 55 18 60 24 7 34 49
42 28 59 42 44 49 36 54
33 11 61 3 70 7 45 29
9 6 4 32 26 3 80 20
122 8 8
386 36 221 161 229 82 173 93
499 595 118 158 417 163 183 366
523 67 210 182 55 120 121 583
142 370 160 22 146 94 206 103
297 378 332 103 436 160 394 516
356 453 448 303 352 600 163 541
164 47 80 139 184 18 199 148
176 392 125 50 232 34 301 212
35 31 74 50 30 53 6 41
61 49 50 20 64 5 17 65
76 43 13 57 13 68 59 2
19 53 20 10 61 34 44 80
51 11 43 69 49 41 63 70
5 80 9 31 37 30 12 56
13 13 57 22 39 4 6 42
8 38 46 48 56 19 32 68
67 8 6
357 230 211 120 294 152
203 183 97 308 98 664
20 158 82 87 132 175
87 45 114 495 177 432
226 72 48 161 10 49
138 157 362 147 99 76
70 135 49 136 142 126
179 596 214 153 601 169
5 72 48 15 36 74
29 55 72 80 79 72
4 78 35 4 24 35
40 44 45 1 24 19
73 52 9 19 4 12
68 28 49 54 59 44
21 48 40 42 73 77
11 7 20 21 80 7
110 8 7
351 122 582 573 380 82 82
208 50 366 182 580 588 481
121 219 84 63 234 83 89
257 246 543 46 558 102 72
659 112 230 168 526 208 26
235 322 202 468 655 242 159
576 95 51 530 612 300 141
234 71 91 385 455 41 191
6 8 46 65 10 40 60
58 5 8 48 37 10 12
79 77 65 50 60 75 71
6 58 74 25 42 78 61
65 20 8 58 14 44 11
65 23 6 32 57 57 68
67 79 21 47 48 37 50
53 44 77 7 43 9 43
121 6 5
374 498 73 215 14
87 172 115 132 200
112 180 160 225 178
82 87 147 654 336
89 109 587 203 123
65 225 92 275 209
33 43 19 18 5
37 61 18 61 58
79 1 11 3 33
28 20 71 78 68
55 15 37 31 39
16 7 31 54 80
49 8 7
120 424 241 16 187 104 201
178 169 265 512 243 93 188
103 239 56 498 80 83 418
77 180 358 582 212 119 313
45 46 211 520 45 83 646
210 516 77 210 240 197 142
345 120 501 18 55 85 287
257 148 77 112 276 99 141
37 37 46 7 43 35 16
48 56 52 57 50 44 24
64 64 48 67 35 11 55
11 56 78 24 70 38 42
14 11 42 38 40 58 78
55 22 57 45 58 6 46
79 56 36 8 10 52 47
66 21 4 19 78 57 5
51 5 5
236 397 403 340 517
211 11 177 73 186
453 72 527 349 494
498 138 81 479 168
76 80 230 79 464
9 34 27 74 54
80 4 64 70 38
39 62 32 52 39
59 10 8 21 57
54 62 60 27 44
133 7 8
347 106 85 571 128 142 647 567
100 103 197 108 94 327 64 168
181 186 593 574 64 220 174 507
422 136 125 420 173 404 625 51
178 125 214 190 463 662 407 65
106 238 52 235 164 88 133 84
93 65 246 93 100 346 240 164
19 52 7 73 72 25 47 71
37 10 50 65 58 71 36 80
79 16 17 13 51 48 44 72
47 19 26 78 66 52 65 6
6 5 18 43 61 67 59 20
78 66 18 42 79 41 21 51
79 39 76 44 65 66 69 63
62 7 5
386 520 168 45 441
126 97 13 164 88
72 172 201 43 149
80 168 192 603 590
77 176 76 230 528
255 647 140 573 256
228 260 316 68 327
37 30 69 5 23
54 23 5 51 64
24 38 5 2 39
73 78 14 43 37
59 70 68 64 18
65 60 35 25 15
43 21 59 33 24
186 5 5
501 182 349 313 147
38 199 178 231 570
319 104 288 50 218
102 179 130 215 81
81 143 49 199 332
22 20 12 66 10
13 33 30 59 38
34 60 7 13 23
6 38 47 41 55
15 13 6 2 18

예상 출력

Case #1: 64.5
Case #2: 78.9
Case #3: 33.4
Case #4: 123.0
Case #5: 0.0
Case #6: 115.8
Case #7: 34.1
Case #8: 0.0
Case #9: 0.0
Case #10: 128.7
Case #11: 91.5
Case #12: 32.6

예제 5

입력

5
188 11 9
463 133 326 72 117 84 63 360 175
407 79 88 583 258 195 25 42 192
133 21 52 163 332 462 194 446 153
120 91 89 179 512 292 206 189 399
79 30 77 26 238 226 117 176 208
166 88 45 266 181 199 265 533 112
203 225 225 138 532 196 19 605 39
183 137 89 163 20 83 142 98 82
213 99 149 134 196 72 466 216 191
58 474 237 591 631 398 540 222 261
138 603 430 118 212 107 91 312 535
40 14 21 23 5 65 21 50 75
21 55 13 26 35 54 22 27 21
43 4 14 63 4 79 73 44 46
19 57 38 55 64 8 25 5 66
25 22 71 9 59 39 27 15 40
39 76 7 69 7 48 76 65 1
34 61 55 35 62 52 10 12 19
75 19 72 11 7 75 69 34 45
51 70 66 62 6 39 35 25 80
7 35 77 31 54 10 23 80 63
58 75 61 3 25 5 46 29 6
73 10 11
169 161 113 97 88 479 45 106 630 168 606
34 480 85 303 115 523 648 202 58 157 119
142 572 466 6 217 183 299 224 205 204 229
441 100 63 50 78 79 196 343 551 73 601
157 242 133 75 216 64 118 44 78 188 207
576 104 195 175 149 155 74 173 203 42 324
211 192 105 193 39 132 80 269 60 102 271
623 72 185 65 269 314 186 522 462 222 661
460 89 119 64 229 410 559 99 131 95 312
230 75 616 228 9 95 85 530 81 240 196
30 3 17 71 75 73 18 59 51 50 47
22 1 53 12 58 13 62 31 48 73 56
12 54 4 1 52 33 42 73 55 55 54
18 53 40 37 42 55 36 25 3 63 52
14 59 70 38 36 25 73 17 75 71 26
45 35 13 63 77 18 41 72 61 6 44
51 49 19 42 15 60 66 24 49 75 15
46 33 53 62 55 26 53 76 37 34 61
65 32 35 34 50 56 58 28 6 49 56
34 2 80 59 5 17 39 44 17 18 49
66 12 11
200 519 142 580 208 144 140 497 495 174 617
139 613 531 238 273 419 553 120 131 168 319
173 132 71 134 118 137 104 376 130 190 117
46 79 76 88 224 549 217 229 158 107 353
200 123 122 201 606 51 117 633 377 156 280
66 366 207 414 222 42 129 344 465 174 474
70 131 153 239 63 102 393 112 388 135 165
238 332 211 241 617 109 158 178 104 192 38
88 112 34 83 86 176 72 32 204 477 191
125 107 146 207 63 79 211 330 304 349 214
157 120 71 62 448 72 464 202 247 18 224
58 140 196 194 327 575 115 197 221 190 125
9 75 39 27 3 51 54 65 10 79 41
4 23 40 22 31 64 50 71 61 50 38
24 78 69 38 61 29 37 51 7 63 25
15 58 57 62 63 49 49 32 73 62 65
6 80 51 51 62 11 7 61 45 44 1
44 55 18 40 29 21 2 15 50 64 17
26 31 10 39 3 40 54 72 33 44 66
47 6 59 79 31 15 39 41 33 52 8
59 32 26 54 24 15 14 31 52 77 59
4 36 61 46 45 46 68 54 6 20 55
69 63 13 36 51 61 30 6 59 5 65
13 23 7 42 52 77 55 72 44 17 44
194 10 10
631 180 407 75 620 270 236 547 561 106
144 137 158 250 88 67 509 469 217 82
441 43 19 151 252 46 235 137 125 71
595 179 9 147 174 271 156 413 150 234
84 80 582 168 69 514 101 212 284 159
137 193 29 206 87 218 113 502 78 172
426 94 102 39 413 52 41 482 47 264
48 205 143 583 43 46 184 199 211 182
43 141 200 227 274 50 247 119 72 415
256 233 487 114 18 121 110 258 77 419
33 35 61 62 31 74 73 51 21 62
40 51 20 37 22 9 69 52 33 27
73 17 8 45 11 3 57 73 59 45
70 12 4 40 15 72 1 52 24 46
51 72 51 23 37 40 19 45 8 80
68 12 11 74 58 4 33 18 58 24
37 24 58 21 16 2 32 44 9 55
14 22 74 5 16 26 70 53 34 79
1 24 43 71 23 31 53 42 35 20
68 67 66 27 7 15 80 30 32 52
49 12 11
468 570 192 87 88 93 550 160 168 416 578
215 285 35 154 144 107 267 77 256 586 134
82 171 440 156 128 305 149 38 237 449 69
293 277 530 207 220 473 230 140 84 58 596
152 68 516 120 340 431 154 194 50 224 91
327 248 57 8 240 346 172 275 113 580 79
630 89 254 162 28 214 123 52 97 137 92
194 168 122 41 96 165 118 246 52 178 207
315 553 387 216 454 221 73 59 255 49 196
75 504 337 225 125 474 81 90 545 295 105
168 246 461 414 197 92 86 456 106 493 222
90 122 189 439 35 416 134 479 188 509 105
16 64 70 8 75 70 22 18 45 55 70
16 60 8 58 74 34 45 11 62 25 75
46 37 47 17 75 59 17 1 80 32 45
38 33 57 14 62 1 46 6 76 42 69
49 28 76 78 59 65 24 74 34 16 72
9 7 3 7 14 44 80 39 78 61 51
55 17 18 17 21 76 22 24 55 35 30
76 34 30 12 65 75 10 67 36 48 64
26 27 1 39 42 80 53 43 67 39 6
66 58 30 14 23 74 76 57 20 79 60
58 75 18 28 27 20 15 75 61 77 40
62 80 48 43 29 72 12 42 19 9 51

예상 출력

Case #1: 175.0
Case #2: 0.0
Case #3: 0.0
Case #4: 114.6
Case #5: 70.7

예제 6

입력

2
9950 2 2
10000 10000
10000 51
1 1
1 1
9950 3 3
10000 10000 10000
10000 10000 10000
10000 10000 10000
9950 9950 9950
9950 9950 9950
9950 9950 9950

예상 출력

Case #1: 1004.9
Case #2: 0.0

예제 7

입력

3
1000 1 100
1050 1040 1030 1020 1010 1000 990 980 970 960 950 940 930 920 910 900 890 880 870 860 850 840 830 820 810 800 790 780 770 760 750 740 730 720 710 700 690 680 670 660 650 640 630 620 610 600 590 580 570 560 550 540 530 520 510 500 490 480 470 460 450 440 430 420 410 400 390 380 370 360 350 340 330 320 310 300 290 280 270 260 250 240 230 220 210 200 190 180 170 160 150 140 130 120 110 100 90 80 70 60
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
800 100 1
900
892
884
876
868
860
852
844
836
828
820
812
804
796
788
780
772
764
756
748
740
732
724
716
708
700
692
684
676
668
660
652
644
636
628
620
612
604
596
588
580
572
564
556
548
540
532
524
516
508
500
492
484
476
468
460
452
444
436
428
420
412
404
396
388
380
372
364
356
348
340
332
324
316
308
300
292
284
276
268
260
252
244
236
228
220
212
204
196
188
180
172
164
156
148
140
132
124
116
108
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
500 1 100
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 200 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

예상 출력

Case #1: 118.0
Case #2: 237.6
Case #3: 418.0

예제 8

입력

50
137 4 3
254 254 769
16 52 266
104 319 559
57 228 602
18 24 87
1 44 65
60 78 11
43 71 79
228 2 2
278 106
61 199
35 42
12 40
61 1 3
111 696 151
9 54 58
179 3 4
229 200 107 98
134 239 118 818
205 166 866 128
13 7 36 68
17 23 81 11
21 100 29 2
192 1 1
518
32
266 1 1
316
54
109 1 2
177 384
92 47
198 3 4
609 866 238 221
503 10 575 95
298 79 212 230
28 90 70 99
43 10 3 86
71 54 61 30
74 3 3
307 247 84
99 251 737
56 103 567
67 58 62
88 30 23
43 19 96
6 2 4
224 704 198 184
382 580 778 448
72 7 100 92
46 64 48 8
115 1 3
223 105 144
23 4 8
170 3 2
220 343
91 464
235 740
39 51
5 10
52 100
17 2 4
125 195 151 301
667 196 239 215
51 18 37 54
62 96 24 86
8 1 2
141 167
26 60
213 1 2
641 139
35 48
108 1 2
158 706
12 7
224 3 3
274 83 250
334 55 53
204 223 237
69 55 96
98 14 8
46 94 88
280 2 3
330 234 231
902 226 137
81 11 14
11 1 47
1 3 1
213
202
605
30
62
72
173 2 2
532 28
331 263
86 3
96 31
154 1 2
244 142
83 39
49 2 1
178
467
11
28
163 4 4
213 317 87 297
68 350 801 433
197 208 49 242
684 31 318 259
94 77 58 76
64 29 26 61
35 57 8 61
74 27 19 58
239 2 1
289
440
96
84
106 1 1
229
68
146 1 1
196
12
178 3 1
228
267
255
14
43
88
233 2 4
283 395 709 716
68 106 86 280
66 45 75 28
20 93 10 34
212 2 4
262 298 143 249
237 265 262 641
5 2 99 73
38 41 76 81
212 4 2
307 105
132 69
476 362
43 220
74 84
74 26
69 7
2 91
185 1 1
235
100
193 2 2
243 179
321 156
25 42
83 16
54 2 3
846 664 282
132 134 272
44 6 86
30 14 58
275 4 3
325 640 108
308 105 846
289 97 104
306 227 250
9 81 32
86 87 81
90 51 85
74 31 48
140 1 1
190
40
157 2 1
483
488
6
49
31 4 3
147 439 228
192 252 152
50 331 494
70 227 187
37 7 83
16 71 72
20 96 39
32 7 77
213 1 1
714
69
295 3 2
345 151
739 839
199 723
57 16
32 100
17 61
87 4 3
137 179 280
82 26 250
27 124 480
118 49 213
20 79 84
35 2 16
7 99 50
12 32 81
53 2 2
103 597
173 263
2 33
30 51
161 1 1
700
96
118 3 4
718 255 126 313
283 176 198 106
269 875 195 321
83 12 89 83
63 15 93 35
4 81 100 95
34 3 3
111 188 388
134 188 334
127 133 187
52 90 66
44 1 94
61 92 65
269 1 1
319
47
186 3 3
451 86 229
166 266 306
480 167 204
28 46 63
38 25 39
4 27 59
247 3 3
939 186 230
295 127 182
486 747 232
72 81 1
60 8 51
57 83 59
68 1 1
595
30
289 4 2
339 55
176 250
280 276
87 266
68 29
30 5
48 38
85 80
184 2 2
234 194
691 854
52 17
89 77

예상 출력

Case #1: 0.0
Case #2: 28.2
Case #3: 0.0
Case #4: 27.3
Case #5: 0.0
Case #6: 0.0
Case #7: 0.0
Case #8: 5.6
Case #9: 0.0
Case #10: 0.0
Case #11: 8.0
Case #12: 0.0
Case #13: 0.0
Case #14: 0.0
Case #15: 13.4
Case #16: 0.0
Case #17: 10.0
Case #18: 20.3
Case #19: 0.0
Case #20: 0.0
Case #21: 16.2
Case #22: 0.0
Case #23: 0.0
Case #24: 0.0
Case #25: 0.0
Case #26: 0.0
Case #27: 0.0
Case #28: 1.3
Case #29: 0.0
Case #30: 53.0
Case #31: 0.0
Case #32: 9.7
Case #33: 0.0
Case #34: 11.8
Case #35: 0.0
Case #36: 0.0
Case #37: 0.0
Case #38: 0.0
Case #39: 0.0
Case #40: 0.0
Case #41: 0.0
Case #42: 0.0
Case #43: 0.0
Case #44: 0.0
Case #45: 0.0
Case #46: 11.0
Case #47: 7.5
Case #48: 0.0
Case #49: 20.3
Case #50: 0.0