Untitled

Ông A 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 ông A 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 ông A >= số lượng lính tại cổng đó. Có các lưu ý:
+ Ông A 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

Điều kiện input: số cổng <=20
	-Số lính và chi phí đi qua >=2 và <=1000
Tìm chi phí nhỏ nhất để ông A có thể đi qua đoạn đường B

VD: Có 7 cổng
	1	2	3	4	5	6	7
Số binh sĩ	10	70	80	20	50	30	10
Chi phí	100	5	15	60	90	80	10
 



Có thể tính chi phí đi nhỏ nhất
	1	2	3	4	5	6	7
Số binh sĩ	10	70	80	20	50	30	10
Chi phí	100	5	15	60	90	80	10
Chọn pp	Pass	Hire	Hire	Battle	Battle	Battle	Pass
Chi phí	100	110	140				150



5
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

#1 150
#2 3000
#3 2370
#4 4721
#5 8231