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