Có n người cần qua bên kia cầu trong đêm. Vì cầu yếu nên chỉ đi một lúc tối đa được hai người. Trong đêm tối họ phải dùng đèn nhưng cả nhóm chỉ có 1 c

Có n người cần qua bên kia cầu trong đêm. Vì cầu yếu nên chỉ đi một lúc tối
đa được hai người. Trong đêm tối họ phải dùng đèn nhưng cả nhóm chỉ có 1 cái
đèn. Vì vậy mỗi lần hai người cầm đèn qua sông thì phải có một người cầm đèn
quay trở lại. Mỗi người qua cầu với các tốc độ lần lượt là: a1, a2, a3,…, an giây.
Hai người đi cùng nhau thì sẽ đi theo vận tốc của người đi chậm hơn. Hỏi để tất cả
n người đều qua sông được thì phải tốn ít nhất là bao nhiêu giây?
Dữ liệu vào: Cho bởi tệp QUACAU.INP, gồm 2 dòng
– Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 100)
– Dòng thứ 2 gồm n số nguyên a1, a2, a3,…, an (1 ≤ ai ≤ 100), mỗi số cách nhau
một khoảng trắng.
Dữ liệu xuất: Cho bởi tệp QUACAU.OUT, gồm 1 dòng là thời gian ít nhất để n
người đi qua cầu. Rút gọn