Bài tập

Khi hành lang cứu trợ đã được xác định, trung tâm cần chuyển từ hoạt động cơ động sang vận hành lâu dài và mở rộng hệ thống cứu trợ. Một mạng vận chuyển cố định được xây dựng để duy trì phân phối vật tư lâu dài, phục vụ đồng thời nhiều điểm phân phối.

Hệ thống mạng vận chuyển cố định gồm \(N\) điểm được đánh số từ \(1\) đến \(N\) và \(N-1\) đoạn đường hai chiều, mỗi đoạn nối trực tiếp \(2\) điểm. Giữa \(2\) điểm bất kỳ trong hệ thống luôn tồn tại đường đi và hệ thống được xem như một cây. Điểm \(1\) là trung tâm điều hành. Mỗi điểm \(i\) có chỉ số hiệu quả là \(A_i\) nếu được chọn làm điểm phân phối vật tư. Chỉ số này có thể có âm do điều kiện mặt bằng, nhân lực hoặc chi phí vận hành tại điểm đó không thuận lợi. Mỗi đoạn đường nối trực tiếp từ điểm \(u\) đến điểm \(v\) có một chi phí kích hoạt \(c\). Để phục vụ một điểm phân phối \(v\), tất cả các đoạn trên đường đi từ điểm \(1\) đến điểm \(v\) phải được kích hoạt. Một đoạn chỉ phải trả chi phí kích hoạt một lần, kể cả khi đoạn đó đồng thời phục vụ nhiều điểm phân phối.

Trung tâm cần xây dựng phương án chọn đúng \(K\) điểm làm điểm phân phối vật tư. Giá trị của một phương án bằng tổng chỉ số hiệu quả của \(K\) điểm được chọn trừ đi tổng chi phí của tất cả các đoạn phải kích hoạt.

Yêu cầu: Hãy giúp trung tâm tìm một phương án có giá trị lớn nhất.

Input

• Dòng \(1\) chứa hai số nguyên \(N, K\) \((1 \le N \le 5 \times 10^4; 1 \le K \le \min(N, 50))\).
• Dòng \(2\) chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) \((-10^9 \le A_i \le 10^9)\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, c\), biểu diễn đoạn đường hai chiều nối trực tiếp từ điểm \(u\) đến điểm \(v\) có chi phí kích hoạt \(c\) \((1 \le u, v \le N; 1 \le c \le 10^9)\).

Output

• Ghi ra một dòng chứa một số nguyên duy nhất là giá trị lớn nhất của phương án tìm được.

Example

8 3
-6 5 14 6 16 2 13 11
1 2 2
2 3 13
1 4 5
3 5 17
5 6 11
5 7 5
4 8 14

6

Scoring

• Subtask 1 (\(15\) điểm): \(N \le 20\).
• Subtask 2 (\(20\) điểm): Cây có đúng \(2\) đỉnh lá.
• Subtask 3 (\(20\) điểm): \(N \le 2000, K \le 20\).
• Subtask 4 (\(45\) điểm): Không có ràng buộc gì thêm.

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.

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.