Question

Bài 4: Bán vé.

Có N người xếp hàng mua vé, đánh số 1 đến N theo thứ tự đứng trong hàng. Thời gian phục vụ bán vé cho người thứ i là t_i. Mỗi người cần mua một vé nhưng được quyền mua tối đa 2 vé, vì thế một số người có thể nhờ người đứng ngay trước mình mua hộ vé. Người thứ i nhận mua vé cho người thứ i+1 thì thời gian mua vé cho 2 người là r_i.

Yêu cầu: Tính thời gian nhỏ nhất để bán vé xong cho N người.

Dữ liệu vào: Đọc từ file TICK.INP

·        Dòng thứ nhất ghi số N.

·        Dòng thứ hai ghi N số nguyên dương t₁, t₂, …, t_N

·        Dòng thứ ba ghi N – 1 số r₁, r₂, …, r_N-1

Dữ liệu ra: Kết quả ghi ra file TICK.OUT

·        Dòng thứ nhất ghi tổng thời gian phục vụ bán vé

·        Các dòng tiếp theo ghi chỉ số của các khách hàng cần rời khỏi hàng, mỗi dòng 10 số, ngược lại nếu không có ai rời khỏi hàng ghi số 0.

Giới hạn:

1 < N  ≤ 2000.

Ví dụ:

TICK.INP	TICK.OUT
5 2 5 7 8 4 3 9 10 10	17 2 4