ICPC North America Qualifier 2015, Problem G
A group of friends snuck away from their school campus, but now they must return from the main campus gate to their dorm while remaining undetected by the many teachers who patrol the campus. Fortunately, they have an invisibility cloak, but it is only large enough to cover two people at a time. They will take turns as individuals or pairs traveling across campus under the cloak (and by necessity, returning the cloak to the gate if others remain). Each student has a maximum pace at which he or she is able to travel, yet if a pair of students are walking under the cloak together, they will have to travel at the pace of the slower of the two. Their goal is to have everyone back at the dorm as quickly as possible.
As an example, assume that there are four people in the group, with person able to make the trip in
minute, person
able to travel in
minutes, person
able to travel in
minutes, and person
able to travel in
minutes. It is possible to get everyone to the dorm in
minutes with the following plan:
and
go from the gate to the dorm together (taking
minutes)
returns with the cloak to the gate (taking
minute)
and
go from the gate to the dorm together (taking
minutes)
returns with the cloak to the gate (taking
minutes)
and
go from the gate to the dorm together (taking
minutes)
Input Specification
The input is a single line beginning with an integer, . Following that are
positive integers that respectively represent the minimum time in which each person is able to cross the campus if alone; these times are measured in minutes, with each being at most
. (It is a very large campus!)
Output Specification
Output the minimum possible time it takes to get the entire group from the gate to the dorm.
Sample Input 1
2 15 5
Sample Output 1
15
Sample Input 2
4 1 2 7 10
Sample Output 2
17
Sample Input 3
5 12 1 3 8 6
Sample Output 3
29
Comments