ACM 2009 - Fence relicts

Problem F. Fence relicts ≡

problems
details
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	2 sec
Input file:	input.txt	Memory limit:	64 Mb
Output file:	output.txt

Statement

The Nearsea region has a large forest, where many relict trees grow. The local government decided to create a reservation park with the area between 0 and S square meters. The park must have a shape of rectangle with the sides parallel to coordinate axises.

Environment activists surveyed the forest and found out that it contained N relict trees located at coordinates (x_i, y_i), measured in meters.

Find such park location and size that the number of relict trees inside of it or on its boundary is maximum possible.

Input file format

Input file contains integers N S followed by N pairs of integers x_i y_i.

Output file format

Output file must contain integers x_a y_a x_b y_b — coordinates of the two opposite corners of the park. If there is more than one optimal solution, output any of them.

Constraints

1 ≤ N ≤ 500, −10⁴ ≤ x_i, y_i ≤ 10⁴, 1 ≤ S ≤ 10⁹

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`5 100 0 0 10 0 10 10 0 10 15 10`	`0 0 10 10`
2	`3 2 0 0 10 0 20 0`	`0 0 20 0`