Bài tập

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

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.

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.

Tại một buổi tiệc kết bạn, có \(N\) người tham gia. Mỗi người đều bí mật gửi một tờ giấy ghi tên người mà mình có cảm tình và muốn được làm quen. Nếu một người không có ai đặc biệt trong lòng, họ sẽ ghi tên chính mình.

Mỗi người tham gia cũng cam kết rằng nếu được ghép đôi với bất kỳ ai (không cần đúng người mình thích), họ sẽ trả một khoản phí nhất định cho ban tổ chức để hỗ trợ kinh phí tổ chức các buổi tiệc tiếp theo.

Ban tổ chức sẽ thực hiện việc ghép cặp, mỗi cặp gồm hai người \((u, v)\) sao cho ít nhất một trong hai người có cảm tình với người kia, tức là \(a_u = v\) hoặc \(a_v = u\). Một người chỉ được tham gia vào nhiều nhất một cặp.

Hãy giúp ban tổ chức tìm cách ghép các cặp sao cho tổng số tiền thu được là lớn nhất có thể.

Input

Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 10^5)\) --- số người tham gia buổi tiệc.

Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) \((1 \le a_i \le N)\) --- với \(a_i\) là người mà người thứ \(i\) có cảm tình. Nếu \(a_i = i\) thì người thứ \(i\) không có cảm tình với ai cả.

Dòng thứ ba chứa \(N\) số nguyên \(b_1, b_2, \ldots, b_N\) \((0 \le b_i \le 10^9)\) --- với \(b_i\) là số tiền người thứ \(i\) sẽ trả nếu được ghép vào một cặp bất kỳ.

Output

In ra một số nguyên duy nhất --- tổng số tiền lớn nhất mà ban tổ chức có thể nhận được nếu ghép các cặp theo đúng quy tắc.

Example

5
2 3 1 1 1
1 2 3 4 5

11