레이팅 미적용A Parisian entrepreneur has just opened a new restaurant "Au bon cordon bleu", named after a famous French recipe. However, no one has any idea of which wine would be appropriate with such a dish. The entrepreneur plans to sample many different wines in order to build the wine menu.
The various bottles of wine he plans to taste can be obtained from different wine merchants located in or around Paris. Being a very sensitive product, high-quality wine can only be transported by highly trained couriers on motorbikes. Therefore, those couriers are very expensive.
A courier can be used for the transportation of several wine bottles, but can transport only one bottle at a time. All couriers get paid at the same fixed rate: one euro per kilometer. The distance function used is the Manhattan distance (also known as taxicab metric) of every individual segment of the trip: the distance from a point \((x_1, y_1)\) to a point \((x_2, y_2)\) is \(|x_1-x_2|+|y_1-y_2|\).
A courier in charge of transporting a single wine bottle will get paid as many euros as the sum of the following two (Manhattan) distances: from her base to the wine merchant place, and from the wine merchant place to the restaurant.
Consider a more complex example: a courier in charge of transporting two wine bottles, one after the other. The amount paid will be the sum of the following distances: from his base to the location of the first bottle, then to the restaurant, then to the location of the second bottle, then to the restaurant.
Help the entrepreneur minimize the costs of hiring the couriers. Given a set of Cartesian coordinates corresponding to available couriers, a set of Cartesian coordinates corresponding to the locations of the precious wine bottles they need to collect, and the location of the restaurant, compute the smallest number of kilometers that the couriers will be paid for. There is no obligation to use all available couriers, and bottles can be collected in an arbitrary order.
The input comprises several lines, each consisting of integers separated with single spaces:
- The first line consists of the number \(N\) of wine bottles to collect and the number \(M\) of available couriers.
- The \(N\) following lines consist of the coordinates of each bottle as two integers \(x\) and \(y\).
- The \(M\) following lines consist of the coordinates of each courier's base as two integers \(x\) and \(y\).
- The last line contains the coordinates of the restaurant as two integers \(x\) and \(y\).
Limits
- \(1 \leq N \leq 1\,000\);
- \(1 \leq M \leq 1\,000\);
- all coordinates \((x,y)\) verify \(-1\,000 \leq x \leq 1\,000\) and \(-1\,000 \leq y \leq 1\,000\).
A single integer: the smallest number of euros that needs to be paid to collect all bottles.
2 2
1 0
0 -1
-1 1
2 -1
0 0
5