Untitled

Tất cả vị trí trong vũ trụ được cho bởi tọa độ 2 chiều (X, Y).
Tàu vũ trụ chỉ có thể di chuyển theo hướng song song với trục X hoặc trục Y và mất 1 giây để di chuyển khoảng cách 1 đơn vị.
Do đó, thời gian mà tàu vũ trụ cần để di chuyển từ tọa độ (x1, y1) tới (x2, y2) được tính như sau:
 
Có tất cả N hố đen trong không gian. Ki là thời gian để di chuyển qua mỗi hố đen, mỗi hố đen có Ki khác nhau.
Và hố đen cho phép di chuyển theo 2 chiều.
Để thuận tiện, 2 lối vào của hố đen được gọi là Cổng A và Cổng B.
 
※ Không bắt buộc phải sử dụng tất cả hố đen để di chuyển tới điểm đích. Cũng có thể không cần dùng đến bất kì hố đen nào trong quá trình di chuyển. 
   Cũng không bắt buộc phải di chuyển qua hố đen mặc dù tàu vũ trụ gặp một cổng của hố đen đó.
 

▶ Cho thông tin về điểm bắt đầu và điểm đích (tọa độ) của tàu vũ trụ và thông tin về mỗi hố đen,
hãy tìm thời gian ngắn nhất để di chuyển từ điểm bắt đầu tới điểm đích.
 

[Giới hạn]
1. Số lượng hố đen N lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 5 (0 ≤ N ≤ 5).
2. Thời gian để di chuyển qua một hố đen Ki lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 3,000. (0 ≤ Ki ≤ 3,000)
3. X, Y, tọa độ trong vũ trụ lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 1,000. (0 ≤ X, Y ≤ 1,000)
4. Không có trường hợp nào mà tọa độ của điểm bắt đầu, điểm đích của tàu vũ trụ và tọa độ của những hố đen giống nhau.
 

[Input]
Dòng đầu tiên của là số lượng phép thử T. Từ dòng tiếp theo là thông tin về mỗi phép thử.
Dòng đầu tiên của mỗi phép thử là số lượng hố đen N.
Dòng thứ 2 là điểm bắt đầu [x1, y1] và điểm đích [x2, y2] của tàu vũ trụ.
Từ dòng thứ 3 tới dòng thứ ‘N+1’ là thông tin về mỗi hố đen.
Tọa độ [x, y] của Cổng A và [x, y] của Cổng B của mỗi hố đen, và thời gian để di chuyển qua hố đen.
 

[Output]
In “#T” cho phép thử thứ T, tiếp theo là một khoảng cách và in câu trả lời (T là số thứ tự của phép thử bắt đầu từ 1).

50
0
0 0 60 60
1
0 0 2 0
1 0 1 2 0
1
0 0 60 60
40 40 20 20 10
2
100 50 10 5
80 40 10 6 10
80 10 70 40 5
3
500 500 1000 1000
501 501 999 999 1000
1 1 499 499 100
1000 999 0 0 200
1
252 854  366 380
242 449  680 162 1259
2
59 382  300 172
138 782  647 631 2652
5 692  376 250 1778
2
367 327  15 769
458 876  184 906 2753
201 839  237 914 1319
2
349 891  539 609
745 98  995 52 211
819 578  556 643 958
3
234 844  255 803
487 718  343 942 1782
208 212  815 788 1383
55 665  111 67 2010
3
967 956  183 221
524 23  166 439 1103
165 695  160 159 1609
962 48  784 637 83
3
132 166  344 269
12 988  362 491 1616
334 451  460 52 937
274 814  695 725 1754
5
864 480  355 621
511 700  265 665 2108
56 778  760 899 778
748 184  469 260 340
87 99  187 794 214
485 721  6 833 1390
5
716 105  730 903
618 726  366 901 354
511 458  381 290 2760
709 339  608 935 2389
258 813  20 306 1786
751 925  300 36 809
4
427 186  957 6
418 546  129 68 991
717 531  219 739 511
335 696  872 404 2886
114 919  772 883 2139
1
276 721  686 539
345 126  755 149 2120
0
103 186  984 440
1
470 238  174 241
973 934  25 839 281
4
603 856  437 739
8 520  44 221 2391
647 653  202 16 2141
132 859  975 8 629
80 422  596 348 1226
3
122 269  280 23
715 854  968 103 550
130 625  219 762 1302
569 216  213 613 2292
4
119 870  322 958
265 632  990 182 1817
289 300  288 572 340
153 635  693 203 669
168 647  40 443 2517
1
854 395  198 415
706 331  272 19 2021
4
860 206  795 355
344 60  468 822 1047
833 545  968 44 2117
521 895  417 719 1968
72 730  772 547 2389
0
450 94  637 265
5
535 692  969 762
86 921  753 581 784
679 919  201 948 621
706 549  453 192 2854
604 358  664 855 2508
924 637  134 178 282
2
962 177  909 317
403 663  513 658 1342
32 674  610 596 2068
2
325 637  379 737
144 214  110 472 908
957 530  468 734 2260
5
328 263  278 446
129 146  237 907 2338
601 908  402 215 1638
902 165  435 912 1924
948 756  143 49 2021
122 239  765 870 2192
1
838 241  944 892
574 147  146 103 1997
0
804 211  578 557
1
125 738  836 951
332 421  833 970 333
4
62 168  552 21
913 595  642 568 528
340 773  50 550 1560
452 181  668 889 2761
802 209  588 773 915
3
646 858  276 204
917 104  333 317 1495
588 504  970 838 1007
510 507  495 282 2389
4
827 738  392 899
99 140  741 810 906
497 780  483 644 2602
252 312  299 793 235
181 498  354 95 1284
3
44 572  389 805
441 607  389 25 1364
416 846  995 115 2399
620 941  787 59 675
1
132 276  547 199
94 89  658 500 1906
3
145 135  450 976
823 984  383 11 1194
397 441  300 665 2185
334 166  944 440 2329
3
614 843  830 168
366 62  604 187 661
798 949  913 972 2822
940 412  939 615 411
3
462 754  117 71
598 359  173 121 581
860 839  402 676 55
216 737  899 880 595
2
548 853  541 860
84 89  282 752 1566
678 189  195 135 857
1
511 771  591 91
159 897  869 520 1669
1
983 868  785 307
5 641  275 950 814
3
86 313  245 464
578 193  315 525 1224
30 599  865 387 940
814 821  857 177 901
5
73 992  196 827
26 623  997 712 169
921 211  657 143 1137
576 633  291 679 2854
152 84  914 353 1973
255 425  831 443 1593
0
927 872  684 974
5
952 571  77 244
497 885  942 465 1752
609 388  790 316 208
1000 453  534 781 2925
565 662  684 9 2457
952 195  444 858 1627
5
465 529  681 23
884 321  605 227 1322
747 464  494 606 1833
840 735  144 613 477
434 981  8 882 2870
163 657  147 501 1027
5
549 313  923 775
97 893  868 423 2237
378 319  1 735 168
171 926  292 587 1878
705 500  749 739 1563
968 511  96 690 823
5
208 403  82 797
334 626  243 511 884
745 728  682 505 1699
779 303  717 187 2830
93 203  109 108 57
904 378  888 51 2624
5
21 961  161 658
339 38  140 315 1733
428 767  216 222 2386
563 725  204 496 1269
55 121  850 896 1197
145 323  504 105 662


#1 120
#2 2
#3 90
#4 41
#5 305
#6 588
#7 451
#8 794
#9 472
#10 62
#11 1519
#12 315
#13 650
#14 812
#15 710
#16 592
#17 1135
#18 299
#19 283
#20 404
#21 291
#22 676
#23 214
#24 358
#25 504
#26 193
#27 154
#28 233
#29 757
#30 572
#31 879
#32 637
#33 1024
#34 596
#35 578
#36 492
#37 1146
#38 891
#39 1028
#40 14
#41 760
#42 759
#43 310
#44 288
#45 345
#46 1202
#47 722
#48 836
#49 520
#50 443