Trong một mảnh vườn hình chữ nhật có kích thước M×N, người ta chia mảnh vườn thành M hàng và N cột, các hàng và cột tạo thành các ô đơn vị hình vuông có cạnh bằng 1, người ta trồng khoai lang trong những ô đơn vị hình vuông. Trong mảnh vườn này có một chú chuột ở trong hang, chú chuột này cần xác định miền (Hai miền khác nhau không có một cạnh ô vuông nào chung) người ta đã trồng khoai lang có diện tích lớn nhất trong mảnh vườn để đào một đường hầm đến phần diện tích lớn nhất đó. Hãy viết chương trình giúp chú chuột tìm được miền chứa khoai lang nhiều nhất.

Dữ liệu vào:

• Dòng đầu tiên ghi 2 số nguyên dương M và N là kích thước của mảnh vườn.
• Trong M dòng tiếp theo, mỗi dòng có N ký tự 0 hoặc 1, với ý nghĩa 0 là không trồng khoai lang, 1 là có trồng khoai lang

Giới hạn: 1≤M,N≤1000

Kết quả:Một số nguyên là tổng số dây khoai lang của miền có diện tích lớn nhất (giả sử mỗi ô chỉ có tối đa một dây khoai lang)

Ví dụ:

Input 1:

6 6
000111
000011
000011
000011
000011
111000

Output 1:

11

Một dây chuyền sản xuất thiết bị vừa sản xuất được $n$ sản phầm và đã dán nhãn cho mỗi sản phẩm một mã số để tiện quản lý. Mã số được dán cho mỗi sản phầm là một số nguyên dương và không không được có hai sản phẩm bất kỳ nào có mã số trùng nhau. Không may là dây chuyền dán nhãn bị lỗi nên trong những sản phẩm đã dán nhãn có thể có nhiều sản phẩm được dán cùng một nhãn (có mã số giống nhau).

Yêu cầu: Hãy tìm xem trong $n$ sản phẩm đã dán nhãn có ít nhất bao nhiêu sản phẩm cần dán lại để tất cả các sản phẩm đều có mã số khác nhau.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương $n$.
• Dòng thứ hai ghi $n$ số nguyên dương được cách nhau một dấu cách là nhãn của $n$ sản phẩm đã được dán

Giới hạn:

• $1\le n\le {10}^6$
• Nhãn của $n$ sản phẩm là các số nguyên dương có giá trị không vượt quá ${10}^7$

Kết quả: Một số nguyên cho biết số lượng ít nhất sản phẩm cần phải dán lại nhãn

Ví dụ:

Input 1:

7
1 2 2 4 2 5 1

Output 1:

3

Một làng quê có $m$ chàng trai đánh số từ 1 tới $m$ và $n$ cô gái đánh số từ 1 tới $n$. Chàng trai thứ i có chiều cao $a_i$($i=1,2,\dots ,m$), cô gái thứ $j$ có chiều cao $b_j$($j=1,2,\dots n$). Trong một buổi khiêu vũ, người ta muốn chọn ra một số cặp nhảy. Mỗi cặp nhảy gồm đúng 1 chàng trai và 1 cô gái và trong cặp đó, chàng trai phải cao hơn cô gái. Mỗi chàng trai, cô gái trong làng không được tham gia quá 1 cặp nhảy.

Yêu cầu: Tìm một số nhiều nhất các cặp nhảy thỏa mãn yêu cầu trên.

Dữ liệu vào:

• Dòng 1 chứa hai số nguyên dương $m$, $n$
• Dòng 2 chứa $m$ số nguyên dương $a_1$, $a_2$,…, $a_m$
• Dòng 3 chứa $n$ số nguyên dương $b_1$, $b_2$,…, $b_n$

Giới hạn:

• $n,m<=$ ${10}^5$
• Giá trị các phần tử trong hai mảng $a,b$ có trị tuyệt đối không vượt quá ${10}^9$

Kết quả:Một số nguyên duy nhất là số cặp nhảy theo phương án tìm được.

Ví dụ:

Input 1:

3 2
1 2 3
2 3

Output 1:

1