Bài tập

Sau khi phân tích dữ liệu từ các trạm hiện trường tại các khu vực, các tuyến đường di chuyển cần được đánh giá để hình thành hành lang cứu trợ hiệu quả. Có \(N\) khu vực cứu trợ và có \(M\) đường đi một chiều nối trực tiếp giữa các khu vực.

\(N\) khu vực và \(M\) đường đi được mô hình hóa như một đồ thị có hướng gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\) và \(M\) cạnh có hướng, trong đó cạnh \((u,v)\) biểu diễn có đường đi trực tiếp từ đỉnh \(u\) đến đỉnh \(v\). Đỉnh \(1\) là sở chỉ huy và đỉnh \(N\) được xác định là khu vực cứu trợ trọng điểm. Tại đỉnh \(i\) có \(A_i\) đơn vị nguồn lực có thể huy động cho nhiệm vụ. Hành trình của đội cứu trợ xuất phát tại đỉnh \(1\) và phải kết thúc tại đỉnh \(N\). Trên hành trình này, đội cứu trợ đi qua đỉnh nào thì được huy động nguồn lực tại đỉnh đó, có thể đi qua một đỉnh nhiều lần nhưng chỉ huy động nguồn lực tại đỉnh đó \(1\) lần.

Yêu cầu: Hãy xác định tổng nguồn lực lớn nhất có thể huy động được trên một hành trình từ đỉnh \(1\) đến đỉnh \(N\). Luôn tồn tại ít nhất một đường đi từ đỉnh \(1\) đến đỉnh \(N\).

Input

• Dòng \(1\) chứa hai số nguyên \(N, M\) \((2 \le N \le 2 \times 10^5; 1 \le M \le 4 \times 10^5)\).
• Dòng \(2\) chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 10^9; 1 \le i \le N)\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) biểu diễn cho một cạnh có hướng nối trực tiếp từ đỉnh \(u\) đến đỉnh \(v\) \((1 \le u, v \le N, u \ne v)\).

Output

• Ghi ra một dòng chứa một số nguyên duy nhất là tổng nguồn lực lớn nhất có thể huy động được.

Example

5 6
6 5 12 3 8
1 2
1 5
2 3
2 4
3 2
3 5

31

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

36

Scoring

• Subtask 1 (\(15\) điểm): \(N \le 15, M \le 40\).
• Subtask 2 (\(20\) điểm): Đồ thị không có chu trình.
• Subtask 3 (\(30\) điểm): \(N \le 400, M \le 5000\).
• Subtask 4 (\(35\) điểm): Không có ràng buộc gì thêm.

Sau một đợt thiên tai lớn, nhiều khu vực bị chia cắt và hệ thống thông tin liên lạc bị ảnh hưởng. Trung tâm điều hành cứu trợ triển khai một hệ thống hỗ trợ thông minh nhằm nhanh chóng đánh giá hiện trạng, duy trì liên lạc và tổ chức vận chuyển vật tư đến các khu vực cần thiết.

Trước tiên, trung tâm muốn đánh giá mức độ ổn định của hệ thống hỗ trợ thông qua các tín hiệu được truyền về từ các thiết bị. Điểm ổn định của hệ thống càng cao thì việc truyền tin có độ tin cậy càng lớn.

Hệ thống gồm \(N\) thiết bị được đánh số thứ tự từ \(1\) đến \(N\) và bố trí tại \(N\) khu vực khác nhau, mỗi khu vực bố trí \(1\) thiết bị. Thiết bị thứ \(i\) truyền về cho trung tâm một tín hiệu mang giá trị là một số nguyên dương \(A_i\), các giá trị này được lưu thành một dãy theo thứ tự từ \(A_1\) đến \(A_N\). Với một đoạn các giá trị liên tiếp trong dãy từ vị trí \(L\) đến vị trí \(R\), nhịp đồng bộ của đoạn được tính là \(G(L,R) = \gcd(A_L, A_{L+1}, \ldots, A_R)\), trong đó \(\gcd(A_L, A_{L+1}, \ldots, A_R)\) là ước chung lớn nhất của các giá trị \(A_L, A_{L+1}, \ldots, A_R\). Điểm ổn định của đoạn được xác định bởi \(F(L,R) = G(L,R) \times (R-L+1)\). Điểm ổn định của hệ thống là \(\max(F[L,R])\) với \(1 \le L \le R \le N\).

Yêu cầu: Hãy tìm điểm ổn định của hệ thống.

Input

• Dòng \(1\) chứa số nguyên \(N\) \((1 \le N \le 2 \times 10^5)\).
• Dòng \(2\) chứa \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\) \((1 \le A_i \le 10^9; 1 \le i \le N)\).

Output

• Ghi ra một dòng chứa một số nguyên dương là điểm ổn định của hệ thống tìm được.

Example

6
12 17 14 18 18 3

36

Scoring

• Subtask 1 (\(20\) điểm): \(N \le 300\).
• Subtask 2 (\(25\) điểm): \(N \le 5000\).
• Subtask 3 (\(25\) điểm): \(A_{i+1}\) chia hết cho \(A_i\) với mọi \(1 \le i < N\).
• Subtask 4 (\(30\) điểm): Không có ràng buộc gì thêm.

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.

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.