Bạn được giao nhiệm vụ tìm vị trí lớn nhất trong khả năng chi trả để xây dựng một kim tự tháp mới. Để hỗ trợ việc lựa chọn, bạn được cung cấp bản khảo sát một khu đất, đã được chia thành một lưới gồm \(M \times N\) ô vuông. Đáy kim tự tháp phải là một hình vuông có các cạnh song song với các cạnh của lưới.

Bản khảo sát ghi nhận \(P\) chướng ngại vật có thể chồng lấn lên nhau. Mỗi chướng ngại vật được mô tả bằng một hình chữ nhật trên lưới, có các cạnh song song với các cạnh của lưới. Để xây kim tự tháp, mọi ô nằm dưới đáy của nó phải được dọn sạch tất cả chướng ngại vật. Chi phí loại bỏ chướng ngại vật thứ \(i\) là \(C_i\). Khi loại bỏ một chướng ngại vật, phải loại bỏ toàn bộ nó, không được chỉ loại bỏ một phần. Việc loại bỏ một chướng ngại vật không ảnh hưởng đến bất kỳ chướng ngại vật nào khác chồng lấn với nó.

Cho kích thước \(M,N\) của khu đất, mô tả \(P\) chướng ngại vật cùng chi phí loại bỏ từng chướng ngại vật và ngân sách \(B\), hãy viết chương trình tìm độ dài cạnh lớn nhất có thể của đáy kim tự tháp sao cho tổng chi phí loại bỏ chướng ngại vật không vượt quá \(B\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa hai số nguyên lần lượt là \(M\) và \(N\), cách nhau bởi một dấu cách.
• Dòng thứ hai chứa số nguyên \(B\), là tổng chi phí lớn nhất bạn có thể chi trả, tức ngân sách của bạn.
• Dòng thứ ba chứa số nguyên \(P\), là số chướng ngại vật được tìm thấy trong bản khảo sát.
• \(P\) dòng tiếp theo mô tả các chướng ngại vật. Dòng thứ \(i\) trong số này mô tả chướng ngại vật thứ \(i\), chứa năm số nguyên \(X_{i1}\), \(Y_{i1}\), \(X_{i2}\), \(Y_{i2}\), \(C_i\), cách nhau bởi một dấu cách. Các số này lần lượt cho biết tọa độ của ô ở góc dưới bên trái, tọa độ của ô ở góc trên bên phải của chướng ngại vật, và chi phí loại bỏ chướng ngại vật đó.

Ô ở góc dưới bên trái của lưới có tọa độ \((1,1)\); ô ở góc trên bên phải có tọa độ \((M,N)\). Các tọa độ của một chướng ngại vật chỉ các ô ngoài cùng thuộc chướng ngại vật đó, kể cả các ô ở hai góc được cho.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: độ dài cạnh lớn nhất của đáy kim tự tháp mà bạn có thể chuẩn bị. Nếu không thể xây bất kỳ kim tự tháp nào, hãy in \(0\).

Ràng buộc

Các ràng buộc sau áp dụng cho mọi nhóm dữ liệu:

• \(1 \le M,N \le 1\,000\,000\): kích thước của lưới.
• \(1 \le C_i \le 7\,000\): chi phí loại bỏ chướng ngại vật thứ \(i\).
• \(1 \le X_{i1} \le X_{i2} \le M\): hoành độ của các ô ngoài cùng bên trái và bên phải của chướng ngại vật thứ \(i\).
• \(1 \le Y_{i1} \le Y_{i2} \le N\): tung độ của các ô dưới cùng và trên cùng của chướng ngại vật thứ \(i\).

Các ràng buộc theo chỉ số \(i\) áp dụng với mọi \(1 \le i \le P\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: pbs/pbs0a.in, pbs/pbs0b.in.

Ví dụ

6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20

4

13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21

3

Nguồn

IOI 2008, ngày thi thứ hai: Pyramid Base, bản tiếng Anh 1.3. Tác giả đề bài: Richard Peng (Canada). Tập đề bài và lời giải IOI 2008.