Untitled

Hugo đang trền đường về nhà và cần đi qua 1 đoạn đường B.

Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng Hugo có 3 cách lựa chọn.

1. Pass

Trả số tiền quy định ở cổng đó để được đi qua

2. Hire

Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình

3. battle

Điều kiện để đánh nhau là số quân của Hugo >= số lượng lính tại cổng đó. Có các lưu ý:

+ Hugo k được tính vào số lượng của quân

+ Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán.

+ Mỗi trận đánh thì tất cả số binh sĩ đều tham gia.

+ Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước

Input:
Dòng đầu tiên là số lượng trường hợp thử nghiệm

Mỗi trường hợp thử nghiệm sẽ có
          Dòng đầu tiên chứa số lượng cổng N

          N dòng tiếp theo chứa 2 số là số binh lính và chi phí tại mỗi cổng

Output: In ra chi phí nhỏ nhất Hugo có thể đi qua đoạn đường B

Điều kiện input: số cổng <=20

-      2 <=Số lính và chi phí đi qua <=1000

VD:

Input
2

7

10 100

70 5

80 15

20 60

50 90

30 80

10 10

9

600 800

300 400

300 400

1000 400

300 600

100 300

600 300

600 500

1000 300

 

Output:

#1 150

#2 3000

Sample input:
20
7
10 100
70 5
80 15
20 60
50 90
30 80
10 10
9
600 800
300 400
300 400
1000 400
300 600
100 300
600 300
600 500
1000 300
11
1000 10
700 900
400 500
300 10
900 900
300 10
50 900
50 900
700 900
500 900
50 10
20
896 546
543 216
454 310
408 367
40 602
252 582
954 627
850 234
763 479
232 278
301 538
528 508
936 154
629 443
758 336
432 700
882 256
278 738
517 882
317 136
20
410 610
831 909
675 629
421 774
386 869
544 219
492 414
996 557
499 482
231 285
804 978
304 881
489 911
75 315
927 648
252 914
330 396
937 133
495 882
813 717
14
780 374
782 572
748 240
2 733
448 676
33 434
271 348
510 743
113 690
195 846
322 560
794 555
642 923
187 830
14
920 329
986 746
32 60
385 811
146 315
479 943
164 105
387 935
135 831
178 710
227 928
203 725
389 317
783 988
14
341 212
10 563
679 198
139 33
319 106
265 611
962 132
703 185
701 747
929 416
339 131
345 463
669 975
80 602
15
620 487
479 722
516 554
44 779
683 607
718 652
46 458
54 264
170 322
200 970
574 773
964 788
793 55
905 393
592 439
15
226 926
887 434
17 257
418 214
254 86
906 363
968 479
755 40
682 136
878 735
195 671
392 110
597 490
356 123
914 927
16
544 819
810 448
561 926
692 933
287 999
104 556
781 602
357 55
3 831
780 192
66 917
515 535
94 115
761 187
894 552
342 769
15
627 654
148 989
732 126
495 51
236 271
56 297
945 731
4 324
546 211
965 111
397 825
844 100
160 15
670 287
216 335
18
826 585
37 71
866 415
639 764
696 802
632 10
530 758
659 165
32 922
475 235
806 914
268 160
371 251
653 130
315 281
143 46
933 449
58 719
19
307 167
216 90
154 513
356 339
439 622
713 435
137 976
910 414
719 837
703 331
683 507
735 846
27 667
562 118
116 405
388 336
499 326
820 515
658 569
20
443 547
881 9
89 287
215 39
31 580
439 61
952 217
746 76
949 522
882 713
928 12
813 478
495 245
60 543
806 824
594 883
300 959
662 902
667 582
854 69
20
412 397
81 799
237 391
884 756
350 928
707 715
81 636
493 617
959 588
703 916
378 48
647 467
778 592
495 204
218 348
688 948
506 776
544 363
730 526
861 817
20
94 881
892 493
452 419
20 865
15 395
275 137
571 743
857 347
434 948
629 743
66 69
327 818
19 681
447 862
198 985
328 272
596 854
475 25
342 606
779 448
20
559 274
973 447
994 369
898 149
325 855
973 983
59 306
123 41
441 399
429 848
274 132
669 864
805 944
682 522
175 509
116 18
418 675
72 430
472 718
591 511
20
595 259
981 834
193 595
856 520
126 685
210 537
252 807
937 335
501 756
157 793
66 404
363 911
380 509
215 223
366 160
666 916
337 961
52 101
370 99
435 394
20
324 642
197 357
777 715
543 649
707 667
340 467
892 581
185 556
235 141
356 16
458 613
908 250
266 806
103 505
213 249
882 938
612 26
655 549
446 603
777 625

5