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(M_i, M_j). 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<10⁶

Dòng 2: N số nguyên dương M_i cách nhau 1 khoảng trắng (0<M_i <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ụ: