Bài tập

Trong một dự án nghiên cứu địa lý, các nhà khoa học đang so sánh hai bức ảnh \(A\) và \(B\) được chụp từ vệ tinh vào hai thời điểm khác nhau. Cả hai bức ảnh đều được biểu diễn dưới dạng một bảng ký tự kích thước \(M \times N\), các hàng được đánh số từ \(1\) đến \(M\), các cột được đánh số từ \(1\) đến \(N\). Ô \((i,j)\) là giao giữa hàng \(i\) và cột \(j\) chứa một trong các ký tự từ a đến z, trong đó mỗi ký tự đại diện cho một loại địa hình (ví dụ: a là rừng, b là nước, c là đô thị, ...).

Do sự xê dịch của vệ tinh và các yếu tố khác, hai bức ảnh không khớp nhau hoàn toàn. Tuy nhiên, các nhà khoa học tin rằng có những vùng ký tự hình chữ nhật cùng kích thước xuất hiện giống nhau ở cả hai ảnh, vùng hình chữ nhật như thế được gọi là hình chữ nhật chung mẫu. Diện tích của hình chữ nhật chung mẫu là số lượng ký tự trong hình chữ nhật đó.

Cho hai bảng \(A\) và \(B\), hãy tìm diện tích lớn nhất của hình chữ nhật chung mẫu.

Input

• Dòng đầu tiên chứa số nguyên \(T\) \((T \le 10)\) là số lượng testcase. Tiếp theo là \(T\) nhóm dòng, mỗi nhóm mô tả một testcase.
• Dòng thứ nhất của mỗi testcase chứa hai số nguyên dương \(M,N\) \((M,N \le 100)\).
• \(M\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(N\) ký tự chỉ gồm các chữ cái Latinh thường mô tả bảng \(A\).
• \(M\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(N\) ký tự chỉ gồm các chữ cái Latinh thường mô tả bảng \(B\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) ghi một số nguyên là đáp án tương ứng với testcase thứ \(i\).

Example

1
5 6
banana
orange
applep
grapes
cherry
pqpqpq
wxange
wxplep
wxapes
zzzzzz

12

1
1 5
acbcb
cacbc

4

Scoring

• Subtask 1 (25% số điểm): \(M,N \le 10\).
• Subtask 2 (25% số điểm): \(M=1\) và \(N \le 100\).
• Subtask 3 (25% số điểm): \(10 < M,N \le 50\).
• Subtask 4 (25% số điểm): Không có ràng buộc bổ sung.

Một công ty công nghệ cần xử lý lần lượt \(n\) tác vụ theo thứ tự đã cho. Tác vụ thứ \(i\) yêu cầu ít nhất \(a_i\) GB bộ nhớ trong (RAM) và \(b_i\) GB dung lượng lưu trữ (Disk).

Các tác vụ phải được chia thành đúng \(k\) lô gồm các tác vụ liên tiếp. Mỗi lô được xử lý trên một máy chủ có cấu hình cố định là \((x,y)\), trong đó \(x\) là dung lượng bộ nhớ trong và \(y\) là dung lượng lưu trữ. Máy chủ có thể xử lý tác vụ thứ \(i\) nếu \(a_i \le x\) và \(b_i \le y\).

Chi phí thuê một máy chủ cấu hình \((x,y)\) để xử lý một lô là \(x+y\), không phụ thuộc vào số lượng tác vụ trong lô. Sau khi hoàn thành lô, máy chủ được trả lại; nếu cần sử dụng cùng cấu hình cho một lô khác, công ty phải thuê lại từ đầu.

Hãy chia \(n\) tác vụ thành đúng \(k\) lô liên tiếp và lựa chọn cấu hình máy chủ cho từng lô sao cho tất cả các tác vụ đều được xử lý, đồng thời tổng chi phí thuê là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,k\) \((n \le 10^5\), \(k \le \min(n,100)\), \(n \cdot k \le 10^6)\) lần lượt là số tác vụ và số lô.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) \((a_i \le 10^9)\).
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_1,b_2,\ldots,b_n\) \((b_i \le 10^9)\).

Output

• In ra một số nguyên duy nhất là tổng chi phí thuê nhỏ nhất tìm được.

Example

6 3
4 4 2 3 1 1
2 1 3 3 7 6

20

6 3
8 3 3 1 7 6
3 9 6 9 7 7

37

4 2
1 4 5 1
1 1 1 1

8

Scoring

• Subtask 1 (10% số điểm): \(k=2\).
• Subtask 2 (20% số điểm): \(n \le 100\).
• Subtask 3 (20% số điểm): \(100 < n \le 1000\).
• Subtask 4 (25% số điểm): \(b_1=b_2=\ldots=b_n=1\).
• Subtask 5 (25% số điểm): Không có ràng buộc bổ sung.

Cho một dãy số nguyên gồm \(n\) phần tử.

Bạn cần in ra các số nguyên lẻ trong dãy theo thứ tự sau:

• Trước hết là các số lẻ theo thứ tự tăng dần.
• Sau đó là các số lẻ theo thứ tự giảm dần.

Các phần tử trùng nhau vẫn được giữ nguyên. Bỏ qua tất cả các số chẵn.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) \((|a_i| \le 10^9)\).

Output

• In ra một dòng gồm các số lẻ theo thứ tự tăng dần, sau đó theo thứ tự giảm dần.
• Các số được phân cách bởi một dấu cách.
• Nếu dãy không có số lẻ, in ra một dòng trống.

Example

7
1 2 3 4 5 6 7

1 3 5 7 7 5 3 1

5
10 20 30 40 50

Cho một dãy gồm \(n\) số nguyên. Sau khi sắp xếp dãy theo thứ tự tăng dần, phần tử trung vị là phần tử nằm chính giữa dãy. Trong bài toán này, \(n\) luôn là số lẻ.

Hãy tìm giá trị phần tử trung vị của dãy.

Input

• Dòng đầu tiên chứa số nguyên lẻ \(n\) \((1 \le n \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) \((|a_i| \le 10^9)\).

Output

• In ra một số nguyên duy nhất là giá trị phần tử trung vị của dãy.

Example

5
1 5 7 2 9

5

Scoring

• Subtask 1 (30 điểm): \(1 \le n \le 100\) và \(|a_i| \le 10^3\).
• Subtask 2 (70 điểm): Không có ràng buộc bổ sung.