> ------- test 1 ----
> 5 4
> 1 2 40
> 1 4 20
> 2 4 20
> 2 3 30
> 3 4 10
> answer:50（废话，这就是样例）
> ------- test 2 ----
> 3 3
> 1 2 5
> 2 2 100
> 2 3 3
> answer:3
> ------- test 3 ----
> 7 6
> 1 2 10000
> 2 3 10000
> 3 6 10000
> 1 4 8000
> 4 3 8000
> 2 5 6000
> 5 6 6000
> answer:16000
> ------- test 4 ----
> 13 5
> 1 2 46
> 1 3 73
> 1 4 33
> 1 5 20
> 2 3 35
> 2 4 15
> 2 5 86
> 3 2 51
> 3 4 93
> 3 5 35
> 4 2 100
> 4 3 91
> 4 5 11
> answer:152
> ------- test 5 ----
> 22 11
> 1 6 5
> 1 7 3
> 1 3 5
> 6 3 2
> 3 7 2
> 6 4 3
> 6 5 2
> 3 5 5
> 3 9 2
> 7 9 3
> 9 5 1
> 5 4 1
> 4 10 5
> 5 10 2
> 5 2 3
> 5 8 2
> 9 8 3
> 10 2 2
> 2 8 2
> 10 11 5
> 2 11 4
> 8 11 4
> answer:13
> ------- test 6 ----
> 18 12
> 1 3 7
> 1 2 3
> 3 6 1
> 3 5 2
> 2 6 3
> 2 5 3
> 2 4 3
> 6 9 4
> 5 9 2
> 5 8 4
> 5 7 2
> 4 7 3
> 7 10 3
> 9 11 3
> 8 11 2
> 8 10 2
> 10 12 3
> 11 12 4
> answer:6
> ------- test 7 ----
> 150 50
> 1 20 10359
> 1 11 884156
> 11 4 382580
> 20 30 643764
> 4 35 108262
> 4 31 5964
> 30 45 39000
> 20 28 68490
> 45 34 210801
> 31 10 308295
> 20 6 138736
> 20 42 746938
> 34 16 852078
> 31 38 277748
> 6 46 18696
> 30 40 417582
> 34 7 88038
> 28 44 694544
> 11 29 317312
> 11 13 555839
> 6 17 1880
> 31 39 59624
> 42 41 79240
> 6 33 207975
> 20 18 262560
> 42 14 247718
> 16 36 121806
> 41 23 109872
> 33 48 124786
> 39 2 117008
> 20 49 382176
> 44 47 726
> 39 9 137648
> 23 21 277875
> 9 15 309902
> 30 8 54600
> 33 12 201208
> 33 32 907308
> 36 24 261030
> 46 27 117396
> 18 22 818460
> 38 19 567361
> 32 5 483645
> 1 26 319310
> 18 3 143376
> 33 25 335692
> 40 37 188258
> 31 43 483140
> 28 50 111967
> 35 48 372193
> 49 43 491200
> 5 31 248692
> 11 9 517439
> 5 25 13200
> 11 10 7429
> 13 43 475146
> 47 48 311865
> 18 29 203008
> 33 22 126540
> 35 38 110307
> 8 22 745056
> 28 42 575900
> 16 50 292864
> 32 17 476779
> 34 29 390260
> 42 16 347761
> 14 34 347529
> 49 21 238952
> 15 12 9882
> 39 20 577920
> 11 27 87432
> 42 29 389325
> 43 45 47878
> 40 30 74333
> 34 39 409684
> 37 1 708825
> 49 34 79216
> 23 23 120915
> 27 30 239169
> 7 18 13244
> 7 6 599664
> 45 23 34224
> 15 5 300748
> 36 33 494384
> 9 3 37356
> 13 43 184200
> 24 6 665000
> 42 7 60998
> 32 30 77787
> 43 31 5742
> 2 9 340830
> 40 6 34920
> 12 41 338588
> 43 10 387180
> 34 11 359251
> 17 48 498232
> 5 42 540925
> 20 24 148716
> 17 34 546150
> 42 41 410800
> 9 28 485475
> 3 33 225524
> 19 8 226634
> 47 30 163296
> 35 27 406686
> 13 4 271467
> 9 22 341388
> 36 41 379776
> 24 50 848350
> 30 6 386379
> 17 16 352521
> 7 23 568980
> 12 26 5124
> 13 4 151525
> 6 23 589620
> 19 43 55296
> 7 3 182932
> 15 4 104720
> 40 15 496027
> 15 30 25508
> 49 38 87330
> 10 42 377169
> 8 45 331850
> 37 16 359940
> 37 41 36768
> 2 36 400476
> 32 41 803964
> 47 35 149169
> 39 20 14520
> 47 19 26130
> 45 1 19840
> 42 13 225368
> 18 24 141696
> 31 44 140760
> 8 38 599196
> 28 9 237846
> 47 36 301325
> 21 18 27546
> 23 17 208110
> 34 17 263718
> 31 20 372164
> 49 2 498168
> 11 7 323912
> 34 2 102256
> 20 10 207165
> 25 3 71649
> 23 21 156112
> 16 48 840
> 33 8 101052
> 4 18 39879
> answer:894515
> ------- test 8 ----
> 183 15
> 1 2 31
> 1 3 46
> 1 4 26
> 1 5 29
> 1 6 62
> 1 7 25
> 1 8 38
> 1 9 7
> 1 10 39
> 1 11 31
> 1 12 86
> 1 13 92
> 1 14 50
> 1 15 9
> 2 3 43
> 2 4 88
> 2 5 30
> 2 6 14
> 2 7 44
> 2 8 87
> 2 9 68
> 2 10 65
> 2 11 16
> 2 12 68
> 2 13 65
> 2 14 42
> 2 15 2
> 3 2 18
> 3 4 56
> 3 5 49
> 3 6 28
> 3 7 4
> 3 8 44
> 3 9 82
> 3 10 76
> 3 11 70
> 3 12 67
> 3 13 93
> 3 14 19
> 3 15 76
> 4 2 51
> 4 3 5
> 4 5 84
> 4 6 47
> 4 7 63
> 4 8 72
> 4 9 91
> 4 10 65
> 4 11 14
> 4 12 28
> 4 13 44
> 4 14 66
> 4 15 36
> 5 2 27
> 5 3 11
> 5 4 70
> 5 6 74
> 5 7 18
> 5 8 82
> 5 9 14
> 5 10 25
> 5 11 52
> 5 12 29
> 5 13 5
> 5 14 63
> 5 15 64
> 6 2 60
> 6 3 75
> 6 4 65
> 6 5 43
> 6 7 5
> 6 8 49
> 6 9 7
> 6 10 6
> 6 11 6
> 6 12 9
> 6 13 29
> 6 14 11
> 6 15 56
> 7 2 62
> 7 3 28
> 7 4 26
> 7 5 66
> 7 6 100
> 7 8 97
> 7 9 58
> 7 10 2
> 7 11 61
> 7 12 63
> 7 13 7
> 7 14 63
> 7 15 66
> 8 2 32
> 8 3 11
> 8 4 43
> 8 5 63
> 8 6 2
> 8 7 54
> 8 9 68
> 8 10 30
> 8 11 64
> 8 12 23
> 8 13 28
> 8 14 87
> 8 15 27
> 9 2 66
> 9 3 92
> 9 4 54
> 9 5 99
> 9 6 36
> 9 7 55
> 9 8 17
> 9 10 72
> 9 11 88
> 9 12 77
> 9 13 33
> 9 14 24
> 9 15 4
> 10 2 71
> 10 3 33
> 10 4 94
> 10 5 12
> 10 6 9
> 10 7 59
> 10 8 41
> 10 9 82
> 10 11 89
> 10 12 98
> 10 13 53
> 10 14 50
> 10 15 42
> 11 2 38
> 11 3 100
> 11 4 74
> 11 5 19
> 11 6 14
> 11 7 8
> 11 8 58
> 11 9 35
> 11 10 77
> 11 12 52
> 11 13 46
> 11 14 10
> 11 15 35
> 12 2 27
> 12 3 35
> 12 4 94
> 12 5 27
> 12 6 16
> 12 7 99
> 12 8 1
> 12 9 45
> 12 10 2
> 12 11 77
> 12 13 40
> 12 14 95
> 12 15 47
> 13 2 10
> 13 3 90
> 13 4 99
> 13 5 84
> 13 6 95
> 13 7 78
> 13 8 17
> 13 9 35
> 13 10 26
> 13 11 16
> 13 12 24
> 13 14 28
> 13 15 96
> 14 2 80
> 14 3 87
> 14 4 98
> 14 5 32
> 14 6 46
> 14 7 88
> 14 8 52
> 14 9 29
> 14 10 91
> 14 11 55
> 14 12 99
> 14 13 70
> 14 15 81
> answer:571
> ------- test 9 ----
> 199 200
> 1 77 604884
> 1 158 4482
> 77 160 333909
> 158 72 830172
> 160 64 111300
> 72 40 9396
> 77 10 65070
> 40 125 760487
> 77 20 223728
> 10 90 559854
> 160 82 23684
> 20 190 19951
> 40 89 230917
> 72 163 496531
> 163 81 273112
> 10 67 379392
> 82 79 355426
> 1 9 515788
> 64 55 338776
> 72 166 223710
> 79 189 42921
> 40 156 155709
> 64 104 431550
> 79 177 684777
> 67 129 55872
> 166 76 133734
> 81 186 503211
> 82 172 47040
> 76 145 37416
> 166 115 49680
> 129 137 551265
> 55 174 373672
> 67 7 208311
> 160 32 184600
> 1 194 5887
> 190 131 600576
> 174 86 45660
> 125 83 298622
> 115 3 208636
> 189 38 87165
> 64 134 13939
> 129 120 834561
> 9 114 873356
> 83 61 241411
> 125 21 9451
> 32 121 582826
> 114 42 41010
> 1 122 70522
> 10 193 102916
> 137 182 150228
> 64 123 422576
> 86 78 13800
> 89 58 32263
> 114 52 275138
> 182 144 304083
> 58 43 442677
> 166 93 839289
> 43 98 162000
> 61 154 95448
> 43 181 3796
> 189 16 315746
> 125 80 191333
> 89 139 326648
> 129 60 235800
> 61 45 127610
> 172 180 193669
> 156 70 131008
> 104 185 304358
> 61 6 138124
> 79 34 653103
> 20 183 153560
> 158 48 125775
> 80 184 684530
> 166 41 150800
> 48 5 504546
> 145 35 55991
> 21 8 44550
> 160 178 88008
> 83 192 197750
> 98 171 419856
> 61 74 498050
> 174 124 91800
> 77 109 142443
> 82 71 147887
> 98 36 14155
> 58 151 32431
> 9 69 458736
> 193 11 676788
> 124 31 228613
> 185 191 250010
> 185 14 374026
> 81 23 713800
> 8 91 46172
> 109 197 231114
> 98 73 726792
> 194 62 130084
> 129 138 4062
> 131 13 274850
> 69 15 24108
> 61 155 15925
> 192 111 558742
> 61 29 232392
> 158 118 210896
> 73 28 170820
> 111 135 229704
> 137 132 149916
> 194 126 270359
> 123 37 17604
> 138 168 265972
> 137 88 200238
> 132 2 146544
> 82 187 75690
> 172 27 575296
> 21 65 808704
> 82 63 154890
> 137 101 241569
> 14 102 180495
> 109 22 670140
> 191 44 129628
> 38 107 426420
> 28 39 114042
> 40 164 951500
> 180 153 641904
> 20 49 133951
> 49 173 238822
> 109 148 22480
> 98 50 567248
> 44 105 245900
> 93 133 129984
> 36 116 129008
> 178 54 30753
> 183 188 29890
> 194 167 453888
> 135 18 314336
> 144 108 351348
> 35 141 72864
> 10 66 106416
> 16 51 116171
> 125 157 53204
> 178 92 85519
> 16 53 260766
> 2 195 372122
> 92 19 434115
> 197 196 152163
> 69 30 179488
> 174 25 797568
> 7 103 168795
> 2 176 403032
> 49 17 304668
> 93 12 170819
> 3 198 511236
> 98 146 290598
> 31 179 788832
> 40 117 291067
> 38 100 407355
> 23 96 467181
> 183 46 442224
> 144 161 6756
> 13 136 13240
> 171 127 278240
> 30 47 92040
> 137 33 327921
> 132 95 228704
> 93 175 28580
> 14 113 289170
> 154 4 749112
> 62 152 827836
> 146 57 57376
> 19 87 15072
> 179 24 26052
> 126 143 135582
> 154 128 109368
> 66 75 261838
> 91 110 97314
> 103 68 16560
> 15 170 52828
> 170 84 19250
> 125 159 33300
> 129 199 481887
> 4 112 152482
> 14 130 216112
> 185 59 603099
> 127 162 384888
> 44 85 264600
> 137 99 160038
> 55 169 58720
> 36 147 141354
> 163 26 327262
> 5 142 185472
> 129 150 247764
> 105 106 25193
> 158 119 98928
> 130 94 360690
> 33 149 434420
> 31 165 571980
> 65 140 175080
> 163 56 901033
> 8 97 35
> 158 200 633027
> answer:4482
> ------- test 10 ----
> 199 50
> 1 46 250104
> 1 24 899262
> 1 15 80055
> 1 37 50603
> 1 49 37800
> 37 38 320870
> 37 6 86811
> 15 2 22244
> 1 45 181373
> 49 7 3544
> 15 12 403604
> 46 8 690720
> 37 28 263412
> 1 40 71370
> 12 48 28404
> 8 21 7326
> 15 43 332310
> 12 11 690228
> 21 27 75225
> 46 3 442950
> 2 25 297960
> 15 4 267467
> 45 5 13432
> 12 35 141492
> 27 23 215600
> 3 34 369600
> 37 9 4905
> 12 14 300744
> 14 19 364040
> 27 20 382396
> 49 10 641823
> 2 41 81153
> 9 32 167510
> 5 44 271219
> 4 16 11184
> 23 29 275502
> 11 42 432078
> 14 18 16965
> 48 33 273456
> 23 39 139384
> 40 31 97567
> 4 26 188246
> 16 47 138980
> 8 22 172577
> 33 36 111230
> 7 30 21054
> 3 17 41181
> 5 13 528858
> 29 50 240760
> 43 47 277514
> 36 41 842506
> 13 33 186456
> 34 9 21403
> 43 45 459825
> 25 37 336474
> 24 17 141200
> 11 50 513535
> 34 17 504672
> 36 7 4802
> 33 36 867825
> 23 46 438080
> 33 38 472428
> 27 37 137200
> 4 14 12768
> 40 38 559647
> 2 48 738568
> 7 14 164388
> 39 29 200506
> 35 1 197524
> 33 30 1466
> 32 43 47244
> 26 34 146772
> 22 14 375396
> 4 23 362168
> 49 17 155016
> 27 22 231660
> 5 25 367584
> 11 44 781568
> 39 36 356481
> 22 50 597300
> 14 27 8168
> 19 5 5796
> 12 24 107141
> 10 2 3480
> 8 20 13870
> 5 31 537591
> 46 50 682864
> 41 12 36900
> 14 31 385176
> 46 32 438240
> 38 44 278784
> 23 33 24855
> 20 37 124640
> 23 17 56100
> 43 19 22176
> 4 49 434241
> 21 28 137952
> 5 18 161568
> 18 37 176190
> 22 4 309675
> 10 31 619548
> 46 5 206796
> 17 30 195552
> 48 14 479076
> 25 25 100744
> 33 6 308913
> 34 16 70252
> 32 34 60096
> 40 9 58312
> 24 25 199800
> 48 20 940975
> 39 35 604435
> 13 27 437852
> 42 13 82490
> 16 42 60030
> 1 16 695520
> 22 29 544479
> 25 34 347529
> 15 28 559302
> 5 22 77670
> 17 44 334730
> 12 34 172676
> 38 33 640533
> 42 18 245232
> 9 49 134067
> 39 13 59784
> 39 45 452956
> 47 5 156144
> 15 35 62434
> 40 40 66185
> 22 4 72220
> 44 38 9345
> 2 30 52908
> 29 23 775795
> 38 14 561150
> 38 46 221040
> 29 12 122920
> 1 28 754444
> 31 23 297570
> 14 50 729150
> 45 35 133163
> 23 49 618300
> 26 29 312698
> 21 31 127428
> 28 39 259644
> 32 24 84576
> 27 10 3081
> 27 1 125928
> 30 27 465660
> 23 4 198066
> 11 35 536400
> 7 22 763152
> 25 29 31218
> 46 27 197547
> 16 37 176700
> 33 20 46629
> 43 22 486783
> 1 28 797534
> 44 30 483055
> 28 9 144676
> 28 49 172692
> 26 15 273916
> 48 27 72267
> 49 8 107793
> 16 37 648375
> 47 35 450730
> 28 11 97118
> 38 8 128280
> 41 17 16264
> 21 42 7362
> 22 3 38222
> 13 45 25545
> 24 41 87945
> 25 18 641704
> 5 30 865890
> 11 13 91368
> 15 2 294
> 5 39 502860
> 27 42 207162
> 34 37 649272
> 40 3 797760
> 17 46 673816
> 14 37 171133
> 40 41 397432
> 43 26 209860
> 20 13 377578
> 3 22 129602
> 40 16 113982
> 30 46 324170
> 24 14 226278
> 40 37 588795
> 38 38 50015
> 15 10 1438
> 28 46 585600
> 29 22 144485
> 30 41 410167
> 9 43 522180
> 20 44 328968
> 16 34 88950
> answer:2763609
> ------- test 11 ----
> 200 100
> 1 4 17085
> 4 28 189225
> 28 16 63288
> 4 2 759330
> 16 62 414178
> 2 36 329440
> 4 95 583020
> 1 69 197298
> 36 80 826454
> 80 27 113169
> 80 68 46128
> 36 96 314100
> 96 3 144330
> 62 85 606276
> 85 32 533664
> 28 24 228683
> 3 23 41938
> 36 41 235512
> 2 81 186348
> 80 77 673456
> 16 94 53760
> 28 47 116987
> 80 56 23358
> 3 15 226238
> 62 63 641900
> 41 54 67104
> 77 92 18080
> 80 37 18210
> 77 30 63600
> 2 93 528
> 27 7 30618
> 69 66 164679
> 81 60 204435
> 23 59 113924
> 85 61 667234
> 16 12 314560
> 94 73 60540
> 92 43 64864
> 95 42 78672
> 56 39 7450
> 54 31 383474
> 96 8 378144
> 60 21 132550
> 77 45 501228
> 32 34 18296
> 39 83 699100
> 77 74 428168
> 31 78 577348
> 77 44 360308
> 85 72 219516
> 80 25 242208
> 68 38 397244
> 44 84 338688
> 96 76 94952
> 27 64 450300
> 32 51 121770
> 95 79 66774
> 64 82 425295
> 84 90 43204
> 81 65 154175
> 74 40 21280
> 72 26 36400
> 76 18 31994
> 73 46 138437
> 84 98 10650
> 92 70 210120
> 54 11 142410
> 28 10 109740
> 66 14 336050
> 93 35 283272
> 66 48 143118
> 48 58 670842
> 59 75 57928
> 3 89 23560
> 28 53 150960
> 36 71 412850
> 32 97 267540
> 76 33 142679
> 76 5 124960
> 89 20 801073
> 44 55 322368
> 93 22 167139
> 55 57 267267
> 33 17 16659
> 51 87 67580
> 81 13 345840
> 40 9 368874
> 53 50 546845
> 46 52 290168
> 61 86 359904
> 92 29 158116
> 46 49 3084
> 76 19 250523
> 7 6 339957
> 77 88 255360
> 80 67 617056
> 81 91 198496
> 10 99 699152
> 62 100 50268
> 68 33 88892
> 83 70 523625
> 39 28 358620
> 49 80 247150
> 74 4 618017
> 97 42 489
> 16 83 183690
> 19 36 162648
> 95 29 8520
> 51 94 667554
> 73 63 19116
> 22 49 25715
> 89 37 40712
> 9 42 23484
> 38 79 1664
> 20 93 519360
> 39 92 478080
> 68 36 28536
> 33 21 468534
> 79 15 825968
> 86 80 193629
> 97 43 158484
> 10 43 449445
> 9 25 132940
> 79 98 2225
> 77 39 494856
> 90 57 7872
> 92 86 57204
> 1 41 32648
> 32 95 48815
> 4 13 14525
> 33 99 151704
> 6 89 170148
> 74 64 109214
> 21 93 97524
> 82 89 117819
> 68 95 218337
> 36 67 511648
> 95 93 284171
> 89 98 17072
> 7 72 206205
> 10 84 67746
> 2 15 418095
> 25 66 510300
> 31 82 75900
> 84 40 505300
> 66 51 135366
> 31 23 901048
> 74 20 41076
> 85 91 444726
> 13 74 309582
> 48 73 198288
> 33 8 476470
> 7 13 447492
> 96 22 644787
> 61 87 413376
> 5 73 154440
> 56 90 46995
> 40 88 279105
> 32 83 233232
> 23 44 255424
> 85 100 490842
> 73 7 57022
> 39 21 334356
> 96 34 56800
> 32 4 733125
> 70 41 759782
> 13 85 36925
> 49 28 120888
> 54 32 256200
> 85 71 599874
> 75 72 745752
> 53 73 432174
> 73 70 257890
> 92 81 444988
> 76 81 22609
> 67 62 789351
> 4 52 32844
> 24 46 195975
> 34 100 83454
> 77 25 260160
> 95 42 636572
> 2 22 341784
> 65 92 499310
> 33 15 580903
> 73 23 107787
> 83 30 280178
> 32 84 382230
> 79 93 160881
> 68 87 630240
> 93 45 215514
> 72 53 597958
> 6 20 88416
> 59 20 620682
> 63 85 166897
> 40 16 102355
> 70 42 481932
> 10 90 91377
> 68 95 446896
> 44 14 51465
> 48 77 101680
> answer:214412
> ------- test 12 ----
> 0 2
> answer:0