HỌC TIN CÙNG THỦ KHOA

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à: a₁, a₂, a₃,..., a_n 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 nhập:

- Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 100)

- Dòng thứ 2 gồm n số nguyên a₁, a₂, a₃,..., a_n (1 ≤ a_i ≤ 100), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất:

- Là thời gian ít nhất để n người đi qua cầu.