Bài tập

Vân có \(N\) đồ trang sức trên kệ được đánh số \(1, 2, \ldots, N\) từ trái sang phải. Đồ trang sức có nhiều loại khác nhau, được biểu thị bằng số nguyên dương. Món đồ thứ \(i\) trên kệ là loại \(A_i\).

Hôm nay Vân sẽ bay ra nước ngoài gặp gia đình và muốn mang theo càng nhiều đồ trang sức càng tốt. Tuy nhiên, vì đang vội nên Vân phải lấy một khoảng đồ trang sức liên tiếp trên kệ. Nghĩa là Vân sẽ chọn hai chỉ số, \(l\) và \(r\), và lấy tất cả các món đồ trang sức được đánh số \(l, l + 1, \ldots, r - 1, r\). Ngoài ra, do các quy tắc về thuế, an ninh sân bay sẽ vứt bỏ tất cả các loại đồ trang sức mà Vân có nhiều hơn \(S\) món trong đồ mang theo.

Ví dụ: giả sử \(S = 2\), Vân mang theo sáu món đồ trang sức: một loại \(0\), hai loại \(1\) và ba loại \(2\). Vân sẽ mất tất cả các nữ trang loại \(2\) ở sân bay!

Yêu cầu: Hãy giúp Vân chọn \(l\) và \(r\) sao cho cô ấy có thể mang được nhiều đồ trang sức nhất cho gia đình mình.

Input

• Dòng đầu tiên ghi duy nhất một số nguyên \(T \leq 5\) là số lượng trường hợp test. Mỗi nhóm dòng trong số \(T\) nhóm dòng sau bao gồm:
• Dòng một chứa hai số nguyên dương \(N\) và \(S\) (\(S \leq N \leq 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i\) là \(A_i\) (\(A_i \leq 10^5\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên là số đồ trang sức tối đa mà Vân có thể mang ra nước ngoài thăm gia đình.

Example

1
6 2
1 1 4 1 4 4

4

Scoring

\begin itemize

• Subtask \(1\) (15 điểm): \(N \le 300\).
• Subtask \(2\) (15 điểm): \(N \le 1000\).
• Subtask \(3\) (70 điểm): Không có ràng buộc nào khác.
  \end itemize

Trong một chuyến phiêu lưu tới thành phố hiện đại Lumina, cô gái Lan Anh đang đứng trước một dãy các toà nhà chọc trời rực rỡ ánh đèn. Cô quyết định chụp một bức ảnh thật đẹp để ghi lại khoảnh khắc này.

Dãy các toà nhà này có thể được mô tả bởi một dãy số gồm \(n\) toà nhà với chiều cao lần lượt là \(h_1, h_2, \dots, h_n\). Lan Anh sẽ chọn một đoạn liên tiếp của dãy toà nhà này để chụp ảnh. Tuy nhiên, để bức ảnh trở nên đáng giá, đoạn được chọn phải có ít nhất \(k\) toà nhà.

Lan Anh có một tiêu chí rất đặc biệt để đánh giá vẻ đẹp của một bức ảnh: cô thích những toà nhà cao, và còn thích hơn nếu chiều cao của các toà nhà có ước chung lớn! Cụ thể, nếu cô chọn một đoạn từ \(h_l\) đến \(h_r\), gọi \(g\) là ước số chung lớn nhất (GCD) của các chiều cao trong đoạn đó, thì vẻ đẹp của bức ảnh được tính bằng:

Bạn hãy giúp Lan Anh tính ra giá trị vẻ đẹp lớn nhất mà cô ấy có thể đạt được với một bức ảnh chụp ít nhất \(k\) toà nhà liên tiếp.

Input

\begin itemize

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le n, k \le 10^6\)).

• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \dots, h_n\) (\(1 \le h_i \le 10^6\)).
  \end itemize

Output

In ra một số nguyên --- vẻ đẹp lớn nhất có thể đạt được.

Example

6 2
2 1 4 4 4 2

48

4 1
7 3 9 4

81

Scoring

• Subtask 1 (11 điểm): \(n, k \le 100\)
• Subtask 2 (28 điểm): \(n, k \le 5000\)
• Subtask 3 (18 điểm): \(h_i \le 100\)
• Subtask 4 (17 điểm): \(n, k \le 5 \cdot 10^4\)
• Subtask 5 (26 điểm): Không có ràng buộc thêm

Cho một cây có \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\) và gốc của cây là đỉnh \(1\). Một số đỉnh của cây đã được tô màu đen, một số khác thì chưa được tô màu. Ta cần tìm cách tô màu cho tất cả các đỉnh.

Thao tác tô màu được định nghĩa như sau: Chọn một đỉnh \(u\) và tô tất cả các đỉnh \(v\) thành màu đen nếu thỏa mãn các điều kiện sau:

• Đỉnh \(v\) nằm trong cây con gốc \(u\).
• Khoảng cách giữa hai đỉnh \(u\) và \(v\) chính xác là \(i\). (Khoảng cách được định nghĩa là số cạnh ngắn nhất để đi từ \(u\) đến \(v\).)

Chi phí để tô màu một đỉnh có khoảng cách \(i\) là \(c_i\). Trong một thao tác, nếu chọn đỉnh \(u\) mà có nhiều hơn một đỉnh \(v\) cùng cách \(u\) một khoảng cách \(i\) thì tất cả các đỉnh đó sẽ được tô màu cùng lúc với chi phí \(c_i\).

Yêu cầu: Hãy tìm cách tô màu sao cho tất cả các đỉnh đều trở thành màu đen với tổng chi phí nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)).
• Dòng thứ hai gồm \(n\) số \(c_0, c_1, \dots, c_{n-1}\) (\(c_i \leq 10^9\)), với \(c_i\) là chi phí để tô màu ở khoảng cách \(i\).
• Dòng thứ ba gồm \(n\) số \(a_1, a_2, \dots, a_n\). Nếu \(a_i = 0\) thì đỉnh \(i\) chưa được tô màu, nếu \(a_i = 1\) thì đỉnh \(i\) đã được tô màu.
• \(n - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u, v\) mô tả một cạnh của cây.

Output

Một dòng duy nhất ghi số nguyên là tổng chi phí nhỏ nhất để tô tất cả các đỉnh thành màu đen.

Example

5
10 5 1 5 5
0 1 0 0 1
1 2
2 3
2 4
4 5

11

Scoring

• Có 20% số test với \(n \leq 20\).
• Có 30% số test với \(n \leq 200\).
• Có 30% số test với \(n \leq 2000\).
• Số test còn lại không có ràng buộc gì thêm.

Trong một lớp có \(n\) bạn và \(n - 1\) cặp bạn trực tiếp, giữa hai bạn bất kỳ luôn tồn tại một mối quan hệ gián tiếp qua các cặp bạn trung gian này.

Qua một bài kiểm tra, cô giáo nhận thấy bạn thứ \(i\) đã làm được \(a_i\) bài của bài kiểm tra. Bằng một phép thần kỳ nào đó, không có hai bạn nào làm được cùng số lượng bài và mỗi bạn (trừ bạn chỉ làm được 1 bài) đều có ít nhất một người bạn trực tiếp làm được ít bài hơn.

Cô giáo muốn chấm điểm cho các bạn dựa trên thang điểm nguyên từ \(1 \rightarrow k\) sao cho không có hai bạn nào có cùng điểm. Sẽ rất bất công nếu như trong một cặp bạn trực tiếp, bạn này làm ít bài hơn nhưng lại nhận được điểm cao hơn.

Yêu cầu: Hãy tìm số cách chấm điểm hợp lý giúp cô giáo. Hay nói cách khác, gọi \(b_i\) là điểm của bạn thứ \(i\), cô giáo muốn tìm số cách chấm điểm sao cho với mọi cặp bạn trực tiếp gồm bạn \(i\) và bạn \(j\), nếu \(a_i > a_j\) thì \(b_i > b_j\) và ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 10^5\), \(1 \leq k \leq 10^9\)) lần lượt là số bạn và thang điểm của cô giáo.
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên \(i\) và \(j\) (\(1 \leq i, j \leq n, i \ne j\)) thể hiện một cặp bạn trực tiếp.
• Dòng cuối cùng chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq n\), \(a_i \ne a_j\) \(\forall\) \(i \ne j\)) là số bài làm được mỗi bạn.

Output

• In ra một số nguyên duy nhất là số cách chấm điểm hợp lệ modulo \(10^9 + 7\).

Example

1 4
1

4

3 4
1 2
1 3
1 2 3

8

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

1

Scoring

• Subtask 1 (20% số điểm): \(k \leq 10\).
• Subtask 2 (20% số điểm): \(k \leq 10^2\).
• Subtask 3 (20% số điểm): \(k \leq 10^3\).
• Subtask 4 (20% số điểm): \(k = n\).
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.