Trong mùa mưa lũ tại các tỉnh miền Trung, có N bạn học sinh cần sang sông để đi học, với phương tiện là một chiếc thuyền tự lái. Chiếc thuyền tự lái này chỉ chở được tối đa là 2 người trên mỗi chuyến đi. Bạn thứ i nếu sang sông một mình sẽ mất thời gian là M[i]. Bạn thứ i và thứ j cùng sang sông sẽ mất thời gian Max(Mi, Mj). Em hãy lập trình giúp các bạn đó tính thời gian nhỏ nhất có thể để đưa được tất cả các bạn qua sông cho kịp giờ vào lớp.
INPUT: River.inp
Dòng 1: Số học sinh N<106
Dòng 2: N số nguyên dương Mi cách nhau 1 khoảng trắng (0<Mi <1000) là thời giang qua sông của N bạn học sinh.
OUTPUT: River.out
Dòng 1: Thời gian nhỏ nhất để đưa n học sinh qua sông.
Ví dụ:
| River.inp | River.out |
| 7 2 3 5 6 4 10 14 |
45 |