Bài tập

Khải rất yêu du lịch. Một ngày Khải được mẹ cho rất nhiều tiền để bay sang Nhật Bản tham gia các sự kiện về văn hóa Nhật, Khải vô cùng thích thú. Khải đã tìm hiểu kĩ thông tin các sự kiện diễn ra, và cậu nhận thấy rằng nếu cậu tham gia được sự kiện \(i\) thì sẽ tăng lên độ vui vẻ là \(v_i\). Dịp này ở nhật bản có rất nhiều sự kiện được tổ chức, cụ thể có \(N\) sự kiện \(s_1,s_2,…,s_N\) (\(s_i\in [1,K]\)) diễn ra theo thứ tự (có nhiều sự kiện có thể lặp lại). Cá nhân Khải thì lại muốn tham gia các sự kiện theo thứ tự \(t_1,t_2,…,t_M\) (\(t_i\in [1,K]\)), tất nhiên nếu cậu tham gia được sự kiện \(t_i\) thì độ vui vẻ của cậu sẽ được cộng thêm \(v_(t_i)\). Tuy nhiên, việc Khải muốn tham gia các sự kiện theo thứ tự ưa thích dẫn tới việc sẽ có một số sự kiện của Nhật Bản mà Khải không tham gia được hay là các sự kiện mà Khải muốn tham gia cũng không tham gia được. Khải tính ra rằng nếu cậu bỏ qua các sự kiện ưa thích \(t_p,t_(p+1),…,t_q\) (\(q\geq p\), \(q-p+1\) sự kiện ưa thích liên tiếp) thì độ vui vẻ của cậu giảm xuống một lượng \(-(A+(q-p+1).B)\). Một điều nữa, nếu như Khải tham gia hai sự kiện \(s_p\) và \(s_q\) (\(p+2\leq q\)) mà không tham gia sự kiện nào giữa hai sự kiện này thì độ vui vẻ của cậu cũng giảm xuống một lượng \(-(A+(q-p-1)B)\).

Yêu cầu: Tìm độ vui vẻ lớn nhất mà Khải có thể có được.

Input

• Dòng đầu gồm các số nguyên dương \(K,N,M,A\) và \(B\) theo thứ tự (\(K\leq 1000;n,m\leq 5000;-100\leq A,B\leq 0\)).

• Dòng thứ hai chứa \(K\) số nguyên dương \(v_1,v_2,…,v_k\) (\(1\leq v_i\leq 100\)).

• Dòng thứ ba chứa \(N\) số nguyên dương \(s_1,s_2,…,s_N\) (\(s_i\in [0,K]\)).

• Dòng thứ 4 chứa \(M\) số nguyên dương \(t_1,t_2,…,t_M\) (\(t_i\in [0,K]\)).

Output

• In ra kết quả bài toán là độ vui vẻ lớn nhất của Khải.

Example

1 5 3 -5 -4
10
1 1 1 1 1
1 1 1

30

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(K=1; M\leq N \leq 10^3\).

• Subtask \(2\) (\(15\%\) số điểm): \(K=1; N<M\leq 10^3\).

• Subtask \(3\) (\(15\%\) số điểm): \(A=B=0\).

• Subtask \(4\) (\(15\%\) số điểm): \(A=0\).

• Subtask \(5\) (\(15\%\) số điểm): \(B=0\).

• Subtask \(6\) (\(15\%\) số điểm): \(N,M<100\).

• Subtask \(7\) (\(15\%\) số điểm): Không có giới hạn gì thêm.

Cho dãy \(a\) gồm \(n\) số nguyên được đánh chỉ số từ \(1\) đến \(n\). Hãy đếm số cách chọn ba chỉ số \(i\), \(j\) và \(k\) sao cho \(1 \leq i < j < k \leq n\) và \(a_{i} \times a_{j} \times a_{k}\) là số chính phương.

Nhắc lại, số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 5 \times 10^{3})\).

• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{6})\).

Output

• Một dòng duy nhất chứa một số nguyên là số lượng cách chọn thỏa mãn.

Example

5
3 1 3 9 4

4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 5 \times 10^{2}\).

• Subtask \(2\) (\(30\%\) số điểm): \(a_{i} \leq 10^{2}\).

• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Cho một đồ thị có hướng gồm \(n\) đỉnh được đánh chỉ số từ \(1\) đến \(n\) và \(m\) cạnh được
đánh chỉ số từ \(1\) đến \(m\), cạnh thứ \(i\) nối từ đỉnh \(u_{i}\) đến đỉnh \(v_{i}\) có trọng số \(w_{i}\).

Hãy tìm đường đi có nhiều cạnh nhất sao cho tổng trọng số của các cạnh thuộc đường đi này không vượt quá \(W\)

Input

Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(W\). \((1 \leq n \leq 100, 0 \leq m \leq n (n - 1), W \leq 10^{15})\).

Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa 3 số nguyên \(u_{i}\), \(v_{i}\) và \(w_{i}\). \((1 \leq u_{i}, v_{i} \leq n, 1 \leq w_{i} \leq 10^9)\).

Output

Một dòng duy nhất chứa một số nguyên là số cạnh của đường đi tìm được.

Example

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

4

Scoring

Subtask \(1\) \((20\% test)\): \(W \leq 10^4\).

Subtask \(2\) \((40\% test)\): \(n \leq 10\).

Subtask \(3\) \((40\% test)\): không có ràng buộc gì thêm.

Cho bảng chữ kích thước \(m \cdot n\), mỗi ô chứa một kí tự \(A\) hoặc \(B\). Một hình chữ nhật con của bảng được gọi là bảng đẹp bậc \(k\) nếu số lượng kí tự \(A\) và số lượng kí tự \(B\) trong bảng con chênh lệch không quá \(k\).

Yêu cầu:
Cho bảng chữ kích thước \(m \cdot n\) và số nguyên \(k\), hãy tìm bảng con là bảng đẹp lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T(T \leq 5)\) là số bộ dữ liệu.

• \(T\) nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:

• Dòng đầu chứa ba số nguyên \(m, n, k\).

• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\) chỉ gồm kí tự \(A\) hoặc \(B\).

Output

• Ghi ra thiết bị ra chuẩn \(T\) dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được
  tương ứng với dữ liệu vào.

Example

2
3 4 0
AAAA
BBBB
BAAA
3 4 1
AAAA
BBBB
BAAA

8
9

Scoring

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 100\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 2000\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 40000, k = 0\).

• Có \(25\%\) số điểm của bài có \(m \cdot n \leq 60000\).