Rikka is now doing summer intern abroad. Every night, she walks home from school. There is a large crossroad on the shortest path, and in most times, it takes Rikka a long time to wait for the traffic light to turn to green, even though sometimes there are not any cars or pedestrians passing through in the contradict direction. To reduce the waiting time, Rikka wants to help the government reschedule the traffic light.
To make things easier, Rikka does some simplification: Suppose there are n pedestrians, some of them will cross the road vertically and others will cross the road horizontally. The ith pedestrian will arrive at the crossroad after ti seconds.
The traffic light has two possible colors: green and red. The green light means pedestrians can now cross the road vertically while red means crossing the road horizontally is allowed. Initially (i.e., at time 0), the color of the light is green, and the color of the traffic light can be changed at any moment for any times.
For any pedestrian, it will take him/her T1 seconds to cross the road vertically and T2 seconds to cross the road horizontally. Therefore, the ith pedestrian can cross the road at time wi (wi can be a floating number) if and only if wi≥ti and one of the following two conditions is held:
1. The pedestrian wants to cross the road vertically, and at any moment in (wi,wi+T1), the traffic light is green.
2. The pedestrian wants to cross the road horizontally, and at any moment in (wi,wi+T2), the traffic light is red.
Notice that several pedestrians can cross the road at the same time: they will not impact others.
Now, Rikka can schedule the state of the traffic light and the time for each pedestrian to cross the road. She wants to find the optimal valid plan so that the total waiting time is minimized, i.e., ∑ni=1(wi−ti) is minimized. Since ti can be quite large and Rikka does not have enough patience to stay there to control the traffic light, she asks you to help her calculate the answer.
To make things easier, Rikka does some simplification: Suppose there are n pedestrians, some of them will cross the road vertically and others will cross the road horizontally. The ith pedestrian will arrive at the crossroad after ti seconds.
The traffic light has two possible colors: green and red. The green light means pedestrians can now cross the road vertically while red means crossing the road horizontally is allowed. Initially (i.e., at time 0), the color of the light is green, and the color of the traffic light can be changed at any moment for any times.
For any pedestrian, it will take him/her T1 seconds to cross the road vertically and T2 seconds to cross the road horizontally. Therefore, the ith pedestrian can cross the road at time wi (wi can be a floating number) if and only if wi≥ti and one of the following two conditions is held:
1. The pedestrian wants to cross the road vertically, and at any moment in (wi,wi+T1), the traffic light is green.
2. The pedestrian wants to cross the road horizontally, and at any moment in (wi,wi+T2), the traffic light is red.
Notice that several pedestrians can cross the road at the same time: they will not impact others.
Now, Rikka can schedule the state of the traffic light and the time for each pedestrian to cross the road. She wants to find the optimal valid plan so that the total waiting time is minimized, i.e., ∑ni=1(wi−ti) is minimized. Since ti can be quite large and Rikka does not have enough patience to stay there to control the traffic light, she asks you to help her calculate the answer.