We all know the YueYa Lake of HDU. It is very beautiful, especially in the evening. However, most of HDU's ACMers may not know,because they only know where the apartments and the laboratory are and they often get lost when they go to other places even Canteen.
CR was very excited when he knew Spring Festival is Valentine's Day this year. Finally, that day is coming. He pulled out the map of HDU and then walked towards the direction of the YueYa Lake.He knew that today there would be a lot of beautiful MMs. Soon, he arrived and he was so lucky that he met a beautiful girl. The girl told him that she would like to have all the flowers floating on the water of YueYa Lake. She also told him if he fulfilled her this wish she was willing to be his girlfriend! How exciting!
Simply，we can see each of flowers as a point (Pi(xi, yi), 0<xi,yi, i≠j,xi≠xj) in the plane and CR stand at coordinate origin.CR must get all the flowers floating in the water and then go back to coordinate origin.Although our CR knew a little Kungfu of QingKung, it’s also a hard work, because it’s would cost CR |PiPj| calories of energy when he flew from Pi to Pj. Our small CR want to make it a wonderful thing that he spent the least energy. But there is a rule:
Before you reach the rightmost point , you can only visit the points those have the bigger x-coordinate value. For example, you are at Pi now, then you can visit Pj only when xj>xi. But when you reach the rightmost point, the rule has changed, you can only visit the points those have the smaller x-coordinate value than the point you are at now.For example, you are at Pi now, then you can visit Pj only when xj<xi.
Of course CR knew the answer, but what about you, clever ACMers?