Little Q is an enthusiast of rhythm games, and recently he began to play
osu! (standard mode) on his tablet.
In the game, his goal is to hit objects (circles, sliders, spinners, etc.) at the right time, and the more hits are perfectly timed, the more total score he gets. Additionally, since his tablet and this game support multi-finger control, he is able to play with two or more fingers. Here are a few snapshots of the game interface.
During his performance-enhancing play, he suddenly comes up with the following question:
There are several oncoming circles on the interface, whose perfect time to hit are pairwisely distinct, and Little Q wants to hit them at the right time using only two fingers. Besides, he wants to minimize the total cost of moving his fingers, where the cost of moving one finger between two circles is equal to the Manhattan distance between the centers of these two circles, and the total cost is the sum of costs for each finger.
Stunned by your excellent problem-solving capability, he would like to ask you to find the minimum total cost.
By the way, the Manhattan distance between two points
(x0,y0)and
(x1,y1)is defined as
|x0−x1|+|y0−y1|, where
|p|is the absolute value of
p.
For more details about
osu!, you may refer to
http://osu.ppy.sh/help/wiki/Main_Page.