cho.sh

Twin Villages

Select as many village pairs as possible with Manhattan distance at least D and degree at most P per village, then minimize the total distance among maximum selections.

Medium7Dynamic programmingBit manipulationGraphBrute forceNo attempts yetTime limit2sMemory limit128 MB

Problem

The government wants to designate twin-village relationships between pairs of villages so that the villages can communicate and exchange culture.

It wants to choose as many pairs as possible, but all of the following conditions must hold.

  1. Each village may be paired with at most P other villages. A village may also have no relationships.
  2. The distance between two villages chosen as a relationship must be at least D. If the two villages are at (x1, y1) and (x2, y2), their distance is |x1-x2| + |y1-y2|.

Maximize the number of twin-village relationships that satisfy the conditions. If there are several ways to achieve the maximum number, choose one whose total distance over all selected relationships is as small as possible.

Given the positions of all villages and the values P and D, write a program that finds the maximum number of relationships and the corresponding minimum total distance.

Input

The first line contains the number of villages N. N is a positive integer not greater than 10.

Each of the next N lines contains the coordinates of one village, in the order x-coordinate then y-coordinate. Each coordinate is an integer between 0 and 1,000 inclusive.

The last line contains P and D. P is a positive integer not greater than 3, and D is a positive integer not greater than 2,000.

No two villages have the same position.

Output

Print two integers on the first line: the maximum number of twin-village relationships that can be made, and the minimum possible total distance for that maximum number.