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.

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ố 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,\ldots,i_k\) liên lạc được với nhau (tức là có liên lạc giữa bất kỳ hai 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) liên lạc được với nhau.

Hãy tính tổng chi phí tối thiểu để hoàn thành loại dự án được yêu cầu.

Input

• Dòng đầu tiên chứa bốn số nguyên \(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\) ứng với dự án loại \(1\) hoặc \(t=2\) ứng với dự án loại \(2\).
• Dòng thứ hai chứa \(k\) số nguyên dương \(i_1,i_2,\ldots,i_k\) đô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)\).

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

Output

• In ra 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.

Example

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

2

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

4

Scoring

• Subtask 1 (30% số điểm): \(t=1\) và \(k=n\).
• Subtask 2 (30% số điểm): \(t=1\) và \(k=2\).
• Subtask 3 (20% số điểm): \(t=1\) và \(2 < k \le 10\).
• Subtask 4 (20% số điểm): \(t=2\) và \(2 < k \le 10\).

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.