Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

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.

Yêu cầ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 1 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~) cho biết số tác vụ và số lô;
• Dòng 2 chứa ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ (~a_i \le 10^9~);
• Dòng 3 chứa ~n~ số nguyên dương ~b_1,b_2,\dots,b_n~ (~b_i \le 10^9~).

Output

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

Scoring

Sample Input 1

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

Sample Output 1

20

Sample Input 2

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

Sample Output 2

37

Sample Input 3

4 2
1 4 5 1
1 1 1 1

Sample Output 3

8

Notes

Trong ví dụ thứ nhất, chia ~6~ tác vụ thành ~3~ lô liên tiếp là ~[1,2]~, ~[3,4]~, ~[5,6]~. Chi phí thuê nhỏ nhất bằng ~(4+2)+(3+3)+(1+7)=20~.

Trong ví dụ thứ hai, hia ~6~ tác vụ thành ~3~ lô liên tiếp là ~[1]~, ~[2,3,4]~, ~[5,6]~. Chi phí thuê nhỏ nhất bằng ~(8+3)+(3+9)+(7+7)=37~.

Trong ví dụ thứ ba, có ~2~ cách chia ~4~ tác vụ thành ~2~ lô đạt chi phí thuê nhỏ nhất là ~8~.

• Cách 1: ~[1]~, ~[2,3,4]~
• Cách 2: ~[1,2,3]~, ~[4]~

Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

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'.. '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 ở cả hai ảnh giống nhau, 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 đó.

Yêu cầu: 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 chứa ~T~ (~T \le 10~) - số lượng testcase. ~T~ nhóm dòng, mỗi nhóm miêu tả ~1~ testcase.
• Dòng thứ nhất của mỗi testcase chứa ~2~ 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 tìm được tương ứng với testcase thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

12

Sample Input 2

1
1 5
acbcb
cacbc

Sample Output 2

4

Notes

Hình chữ nhật chung lớn nhất là khối ~3 \times 4~ sau:

• ange
• plep
• apes

Ở ~A~ tại hàng ~2-4~, cột ~3-6~

Ở ~B~ tại hàng ~2-4~, cột ~3-6~

Diện tích lớn nhất là ~3 \times 4=12~.

Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Thời gian vừa qua, mưa bão lũ quét và sạt lở đã làm hư hỏng, đứt rất nhiều tuyến cáp quang nối giữa các trạm thu phát sóng trong thành phố.

Theo khảo sát, có ~n~ trạm (được đánh số từ ~1~ đến ~n~) và ~m~ tuyến cáp (được đánh số thứ tự từ ~1~ đến ~m~) hư hỏng nặng cần phải sửa chữa gấp. Chi phí để sửa chữa tuyến cáp thứ ~i~ nối giữa trạm ~u_i~ và trạm ~v_i~ là ~w_i~.

Chính quyền thành phố hiện có hai phương án ưu tiên sửa chữa độc lập, cả hai đều nhắm đến mục tiêu tối ưu hóa tổng chi phí:

• Dự án loại 1: Sửa chữa một số tuyến cáp sao cho ~k~ trạm trọng điểm ~i_1,i_2,\dots,i_k~ liên lạc được với nhau (tức là có liên lạc giữa bất kỳ trạm ~i_u~ và ~i_v~ nào thuộc nhóm này).
• Dự án loại 2: Sửa chữa một số tuyến cáp sao cho ~n-k~ trạm dân sự còn lại (các trạm không nằm trong danh sách ở trạm trọng điểm ở trên) có thể liên lạc được với nhau.

Yêu cầu: Viết chương trình tính toán tổng chi phí tối thiểu để hoàn thành một trong hai loại dự án trên.

Input

• Dòng đầu ghi ~4~ số ~n,k,m,t~ trong đó ~n~ (~n \le 100~) là tổng số trạm thu phát sóng, ~k~ là số lượng trạm trọng điểm, ~m~ (~m \le 1000~) là số tuyến cáp quang, ~t=1~ là dự án loại 1 hoặc ~t=2~ là dự án loại 2;
• Dòng tiếp theo ghi ~k~ số nguyên dương ~i_1,i_2,\dots,i_k~ (Các số đôi một khác nhau);
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i,v_i,w_i~ thể hiện có tuyến cáp nối giữa trạm ~u_i~ và trạm ~v_i~ với chi phí sửa chữa là ~w_i~ (~w_i \le 10^6~).

Output

Một số nguyên duy nhất là tổng chi phí tối thiểu để thực hiện dự án được yêu cầu.

Scoring

Sample Input 1

5 3 5 1
1 2 3
1 2 1
1 3 1
1 5 1
2 4 2
4 1 5

Sample Output 1

2

Sample Input 2

5 3 5 2
1 2 3
1 2 1
1 3 1
1 5 1
2 4 2
4 1 5

Sample Output 2

4

Notes

Lưu ý: Dữ liệu đảm bảo luôn có đáp án.