Flatland government is building a new highway that will be used to
transport weapons from its main weapon plant to the frontline in order
to support the undergoing military operation against its neighbor
country Edgeland. Highway is a straight line and there are
During last days the threat of a nuclear attack from Edgeland has
significantly increased. Therefore the construction office has decided to
develop an evacuation plan for the construction teams in case of a
nuclear attack. There are
Each shelter entrance must be securely locked from the inside to prevent any damage to the shelter itself. So, for each shelter there must be some team that goes to this shelter in case of an attack. The office must also supply fuel to each team, so that it can drive to its assigned shelter in case of an attack. The amount of fuel that is needed is proportional to the distance from the team's location to the assigned shelter. To minimize evacuation costs, the office would like to create a plan that minimizes the total fuel needed.
Your task is to help them develop such a plan.
Input Specification
The first line of the input contains
The third line of the input contains
The amount of fuel that needs to be supplied to a team at location
Output Specification
The first line of the output must contain
Sample Input
3
1 2 3
2
2 10
Sample Output
8
1 1 2
Comments