Gói quà

Tác giả:

Dạng bài

Điểm: 2500 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có \(n\) hộp quà có dạng hình khối và cùng chiều cao bằng \(1\), hộp quà thứ \(i\) (\(1 \le i \le n\)) có đáy là \(a_i \times b_i\). Người ta muốn xếp \(n\) hộp quà vào một hộp cũng có chiều cao bằng \(1\) và có diện tích đáy càng nhỏ càng tốt. Các cạnh đáy của các hộp quà phải đặt song song hoặc vuông góc với các cạnh đáy của hộp đựng quà.

Input

Dòng đầu tiên gồm số nguyên \(n\).
Dòng thứ \(i\) (\(1 \le i \le n\)) chứa hai số nguyên dương \(a_i,b_i\) (\(a_i,b_i \le 10^6\)).

Dữ liệu đảm bảo tồn tại một hình hộp chữ nhật có diện tích đáy bằng tổng diện tích dáy của các hộp quà và chứa được hết tất cả các hộp quà.

Output

Dòng đầu tiên gồm hai số nguyên dương \(W,H\) là kích thước đáy hình hộp để chứa \(n\) hộp quà. Quy ước đặt hộp quà trên hệ trục tọa độ với góc trái dưới là \((0,0)\) và tọa độ phải trên là \((W,H)\).
Tiếp theo là \(n\) dòng, dòng thứ \(i\) (\(1 \le i \le n\)) gồm bốn số là tọa độ phải dưới và phải trên mô tả vị trí đặt hộp quà thứ \(i\).

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n \le 5\).
Subtask \(2\) (\(30\%\) số điểm): \(n \le 10\).
Subtask \(3\) (\(40\%\) số điểm): \(n \le 50\).
Cách tính điểm: Có \(20\) test, mỗi test \(5.0\) điểm. Gọi diện tích dáy của hình hộp cần dùng do thí sinh tìm được là \(c\), \(q\) là tổng diện tích đáy của các hộp quà, khi đó số điểm bạn đạt được cho mỗi test là \(5.0 \times min\{1,\frac{q^2}{c^2}\}\).