Cho một ma trận ~A~ kích thước ~M \times N~ gồm các số nguyên dương. Một hình vuông kích thước ~k \times k~ được trích ra từ ma trận gọi là hình vuông "gần nguyên tố" nếu trong hình vuông đó có tối đa 1 số không phải là số nguyên tố.

Yêu cầu: Tìm diện tích của hình vuông "gần nguyên tố" có kích thước lớn nhất.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~M~ và ~N~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên dương ~A_{i,j}~, giữa các số cách nhau một khoảng trắng.

Output

• Ghi ra một số nguyên duy nhất là diện tích (~k \times k~) của hình vuông lớn nhất tìm được.

Ràng buộc

• ~M \times N \le 10^6~
• ~1 \le A_{i,j} \le 10^6~
• Subtask 1 (25%): ~M, N \le 10~.
• Subtask 2 (25%): ~M, N \le 50~.
• Subtask 3 (25%): ~M, N \le 300~.
• Subtask 4 (25%): ~M \times N \le 10^6~.

Sample Input 1

3 3
2 3 5
7 4 11
13 17 19

Sample Output 1

9

Giải thích: Hình vuông kích thước ~3 \times 3~ chứa 8 số nguyên tố và chỉ chứa đúng 1 số không phải nguyên tố (là số ~4~). Do đó, hình vuông ~3 \times 3~ thỏa mãn điều kiện. Diện tích lớn nhất là ~3 \times 3 = 9~.

Sample Input 2

2 2
4 6
8 10

Sample Output 2

1

Giải thích: Toàn bộ ma trận đều là hợp số. Các hình vuông ~2 \times 2~ sẽ chứa tới 4 hợp số (không thỏa mãn). Tuy nhiên, các hình vuông ~1 \times 1~ chỉ chứa đúng 1 hợp số, thỏa mãn điều kiện "tối đa 1 số không phải nguyên tố". Diện tích lớn nhất là ~1 \times 1 = 1~.

V? d?

Input

1 10
145417 784913 251491 571229 398557 392981 735451 25537...

Output

1

Cho một dãy số nguyên dương ~A~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Một đoạn con hợp lệ là một dãy các phần tử liên tiếp của dãy sao cho: Không có bất kỳ giá trị nào xuất hiện nhiều hơn ~m~ lần trong đoạn con đó.

Bạn được phép xóa đi nhiều nhất ~k~ phần tử khỏi dãy ~A~. Sau khi xóa, các phần tử còn lại sẽ giữ nguyên thứ tự tương đối ban đầu và dồn lại thành một dãy mới ~A'~. Nhiệm vụ của bạn là phải phân chia toàn bộ dãy ~A'~ thành các đoạn con liên tiếp hợp lệ (các đoạn con không giao nhau).

Yêu cầu: Hãy tìm cách chọn các phần tử để xóa sao cho tổng số lượng đoạn con hợp lệ sau khi phân chia là ít nhất.

Input

• Dòng đầu tiên chứa ba số nguyên ~n, m, k~ (~1 \le m \le n \le 10^5; k \le 300~);
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^5; 1 \le i \le n~).

Output

• Gồm một số nguyên là số dãy con tối thiểu đạt được.

Ràng buộc

• Subtask 1 (20% số điểm): ~k = 0~.
• Subtask 2 (20% số điểm): ~n \le 1000; k \le 20~.
• Subtask 3 (30% số điểm): ~n \le 10^5; k \le 20~.
• Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.

Sample Input 1

5 1 1
2 2 1 2 3

Sample Output 1

2

Giải thích: * Yêu cầu: Mỗi đoạn con không có phần tử nào xuất hiện quá 1 lần (~m = 1~). Xóa tối đa 1 phần tử (~k = 1~).

• Có thể xóa phần tử ở vị trí thứ 4 (số 2). Mảng sau khi xóa thành ~A' = [2, 2, 1, 3]~.
• Khi đó chia ~A'~ thành 2 đoạn con liên tiếp hợp lệ: ~[2]~ và ~[2, 1, 3]~.
• Không có cách xóa nào giúp ta chia được thành 1 đoạn con duy nhất, nên 2 là kết quả tối ưu.

Trong quá trình đổi mới quản lý, trường tiểu học KD tiến hành bầu chọn Ban tự quản. Theo quy định, việc bầu chọn được tiến hành theo qui trình sau: Ban bầu cử lập danh sách tất cả các lớp trong trường và phân các học sinh nam thành các nhóm. Mỗi nhóm sẽ gồm một số lớp liên tiếp nhau trong danh sách. Kết quả của việc phân nhóm là mỗi lớp sẽ thuộc vào đúng một nhóm.

Mỗi nhóm sẽ đề cử ~2~ ứng viên tham gia vào Ban tự quản của trường: một ứng viên là học sinh nam và một ứng viên là học sinh nữ. Tiếp đến, mỗi học sinh sẽ bỏ phiếu chọn một trong hai ứng viên thuộc nhóm của mình. Biết rằng các học sinh nam chỉ bầu cho ứng viên nam và các học sinh nữ chỉ bầu cho ứng viên nữ.

Kết quả kiểm phiếu sẽ được thống kê theo từng nhóm. Ứng viên nam được nhiều phiếu bầu chọn nhất trong nhóm của mình sẽ trúng cử vào Ban tự quản. Trong trường hợp hai ứng viên có cùng số phiếu, cả hai ứng viên đều trúng cử vào Ban tự quản.

Giả sử kết quả bầu cử có ~B~ học sinh nam và ~G~ học sinh nữ được bầu vào Ban tự quản. Theo kinh nghiệm tích lũy từ những năm trước, Ban bầu cử thấy rằng hiệu số ~B - G~ càng lớn thì Ban tự quản làm việc càng hiệu quả. Vì vậy họ muốn cực đại hóa giá trị ~B - G~, tuy nhiên giá trị này không phải tuyệt đối.

Ví dụ: nếu ~B = 2, G = 5~ thì ~B - G = -3~, còn nếu ~B = 3, G = 4~ thì ~B - G = -1~, kết quả thứ hai được tính là tốt hơn.

Trường KD có ~n~ lớp và Ban bầu cử đã lập danh sách các lớp theo thứ tự từ ~1~ đến ~n~. Bây giờ, Ban bầu cử cần tìm cách phân nhóm, mỗi nhóm gồm ít nhất ~l~ lớp (để đảm bảo số thành viên trong Ban tự quản là không quá lớn) và không quá ~r~ lớp (để các học sinh dễ thống nhất khi bầu cử).

Chú ý là các lớp trong mỗi nhóm phải có số thứ tự liên tiếp trong danh sách lớp đã lập, mỗi lớp thuộc đúng một nhóm.

Yêu cầu: Hãy giúp Ban bầu cử tìm cách phân nhóm để kết quả bầu cử cho Ban tự quản hoạt động hiệu quả nhất (giá trị cực đại của ~B - G~).

Input

• Dòng đầu tiên chứa ba số nguyên ~n, l, r~ (~1 \le l \le r \le n~) theo thứ tự là số lượng lớp trong trường, cận dưới và cận trên của số lớp trong một nhóm.

• Dòng thứ ~i + 1~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~b_i~ và ~g_i~ (~1 \le b_i, g_i \le 10000~) là số lượng học sinh nam và số lượng học sinh nữ của lớp thứ ~i~.

• Hai số liên tiếp trên cùng một dòng được cách nhau bởi một dấu cách.

Output

• Ghi ra một số nguyên là giá trị lớn nhất của ~B - G~ có thể đạt được.

Ràng buộc

• ~20%~ số test có ~1 \le n \le 10^4~
• ~80%~ số test còn lại có ~10^4 < n \le 10^5~

Sample Input

5 1 2
7 5
10 1
2 3
2 6
4 3

Sample Output

2

Giải thích:

Một cách phân nhóm tối ưu:

• Nhóm 1: Lớp số 1
• Nhóm 2: Lớp số 2 và lớp số 3
• Nhóm 3: Lớp số 4
• Nhóm 4: Lớp số 5

Theo cách phân nhóm này:

• Nhóm 1: ~1~ học sinh nam trúng cử
• Nhóm 2: ~1~ học sinh nam trúng cử
• Nhóm 3: ~1~ học sinh nam trúng cử
• Nhóm 4: ~1~ học sinh nam trúng cử

Ban tự quản có ~B = 3~ học sinh nam và ~G = 1~ học sinh nữ.

Do đó:

~B - G = 2~.