ITPTIT ICPC 2021

Time limits: 1s

Colder có một mảnh giấy hình chữ nhật có cạnh dọc và ngang tương ứng là  a và b đơn vị. Mảnh giấy được chia thành a x b  ô vuông đơn vị, chiều dọc chia thành  a hàng, các hàng được được đánh số từ  1 đến a  từ trên xuống dưới, chiều ngang được chia thành  b cột đánh số từ 1 đến b từ trái sang phải. Ô nằm giao giữa hàng i và cột j được gọi là ô (i, j).  Có c  ô vuông của mảnh giấy đã được tô màu. Với cặp số (d, e) , Colder muốn chọn một hình vuông trên mảnh giấy ban đầu và cắt mảnh giấy hình vuông này từ mảnh giấy ban đầu thỏa mãn điều kiện sau:

• Mảnh giấy chứa một số nguyên các ô vuông của mảnh giấy ban đầu;
• Mảnh giấy có cạnh chia hết cho d ;
• Mảnh giấy có không quá e ô đã tô màu.

Yêu cầu: Cho thông tin về mảnh giấy ban đầu và cặp số (d,e)  hãy tìm phương án cắt hình vuông thỏa mãn các điều kiện trên mà có cạnh lớn nhất.

INPUT:

• Dòng đầu chứa năm số nguyên a, b, c, d, e  

( e  ≤ c  ≤ a x b; 1  ≤ d  ≤ min(a,b) )

• Dòng thứ k  trong số c dòng tiếp theo chứa hai số nguyên i_k, j_k  mô tả ô đã tô màu.

OUTPUT: Ghi ra một số nguyên là độ dài cạnh hình vuông lớn nhất tìm được.

Ràng buộc:

• Có 1/3 số test tương ứng với a,b  ≤ 20.
• Có 1/3 số test tương ứng với a,b ≤ 200.
• Có 1/3 số test tương ứng với a,b ≤ 6005, c  ≤ 10⁵

EXAMPLE:

Giải thích: 1 cách chọn cắt hình vuông thỏa mãn