🐉PhuocThien (Div. 01)

PhuocThien và uou đang chơi một trò chơi với các con số. uou viết lên bảng một số nguyên dương \(n\) rồi nói rằng một số được gọi là LUCKY nếu tổng các chữ số của nó bằng \(10\). Nhiệm vụ của PhuocThien là đếm xem trong các số từ \(1\) đến \(n\) có bao nhiêu số LUCKY.

Input

• Một dòng duy nhất chứa số nguyên dương \(n\). \((1 \le n \le 10^7)\).

Output

• In ra số lượng số may mắn trong đoạn từ \(1\) đến \(n\).

Example

20

1

100

9

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(n \le 1000\).
• Subtask \(2\) (\(30\%\) điểm): \(n \le 10^4\).
• Subtask \(3\) (\(50\%\) điểm): Không có ràng gì thêm.

Cho một ma trận vuông \(n \times n\) gồm các số nguyên không âm. Hãy đếm xem có bao nhiêu phần tử là số nguyên tố nằm trên đường chéo chính hoặc đường chéo phụ của ma trận. Một phần tử được tính một lần nếu nó thuộc cả hai đường chéo.

Input

• Dòng đầu tiên chứa số nguyên \(n\). \((1 \le n \le 500)\)
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên, là các phần tử của ma trận.
• Các số trong ma trận không vượt quá \(10^6\).

Output

• In ra một số nguyên duy nhất là số lượng phần tử nguyên tố nằm trên hai đường chéo của ma trận.

Example

3
2 4 5
6 7 8
11 10 13

5

8
2 4 5 6 2 3 4 5 
1 5 2 3 2 2 2 1
3 3 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
91 52 14 54 11 35 76 11
125 667 333 111 112 113 114 333
3 1 1 1 1 1 1 3

10

Scoring

• Subtask \(1\) (\(30\%\) điểm): \(1 \le n \le 100\).
• Subtask \(2\) (\(70\%\) điểm): Không còn ràng buộc gì thêm.

Một xưởng sản xuất ghi nhận trong \(n\) ngày liên tiếp hai đại lượng:

• \(a_i\): số nguyên liệu tiêu thụ trong ngày \(i\),
• \(b_i\): số sản phẩm hoàn thành trong ngày \(i\).

Với một đoạn ngày liên tiếp bất kỳ, tỷ lệ hiệu quả của đoạn đó được định nghĩa là: \(\dfrac{\text{Sum } b_i}{\text{Sum } a_i}\)
Hãy tìm tỷ lệ hiệu quả lớn nhất trong các đoạn liên tiếp có độ dài ít nhất \(k\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, k\). \((1 \le k \le n \le 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\). \((1 \le a_i \le 10^6)\)
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n\). \((1 \le b_i \le 10^6)\)

Output

• In ra một số thực là tỷ lệ hiệu quả lớn nhất có thể tìm được.
• Kết quả được làm tròn đến 3 chữ số sau dấu phẩy.

Example

5 2
4 2 3 5 1
6 3 5 7 2

1.600

10 3
1 2 3 4 5 6 7 8 9 10
100 200 1222 5677 3456 5555 6 4 11 5554 

979.200

Scoring

• Subtask \(1\) (\(30\%\) điểm): \(1 \le n \le 1000\).
• Subtask \(2\) (\(70\%\) điểm): \(1 \le n \le 10^5\).

Vào buổi sáng trước ngày đi dã ngoại, PhuocThien và uou được thầy giáo giao phụ trách chuẩn bị đồ dùng cho cả nhóm. Trên bàn có \(n\) món đồ khác nhau, mỗi món đồ thứ \(i\) có khối lượng là \(w_i\) và giá trị hữu ích là \(v_i\). Chiếc ba lô mà thầy đưa cho nhóm có sức chứa tối đa là \(m\), nên không thể bỏ tất cả mọi thứ vào cùng một lúc. PhuocThien muốn chọn đúng \(k\) món đồ để mang theo, vì thầy chỉ cho phép nhóm mang một số lượng đồ vừa đủ để tránh cồng kềnh. Tuy nhiên, không phải cách chọn nào cũng hợp lệ, bởi tổng khối lượng của các món được chọn không được vượt quá \(m\). Nhiệm vụ của bạn là giúp PhuocThien tìm tổng giá trị hữu ích lớn nhất có thể đạt được khi chọn đúng \(k\) món đồ thỏa mãn điều kiện về khối lượng. Nếu không có cách chọn nào hợp lệ, hãy in ra -1.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(k\) (\(1 \le n \le 250\), \(1 \le k \le n\), \(1 \le m \le 2500\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(w_i\), \(v_i\) (\(1 \le w_i \le 1000\), \(1 \le v_i \le 10^9\)) lần lượt là khối lượng và giá trị hữu ích của món đồ thứ \(i\).

Output

• In ra một số nguyên duy nhất là tổng giá trị hữu ích lớn nhất có thể đạt được khi chọn đúng \(k\) món đồ và tổng khối lượng không vượt quá \(m\).
• Nếu không tồn tại cách chọn hợp lệ, in ra -1.

Example

5 10 3
2 6
3 7
4 8
5 9
6 12

22

9 12 1
11 -42
3 -14
10 41
9 16
10 -61
1 45
11 37
10 2
9 -43

45

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le n \le 20\), \(1 \le m \le 50\), \(1 \le k \le n\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le n \le 100\), \(1 \le m \le 500\), \(1 \le k \le 20\).
• Subtask \(3\) (\(50\%\) điểm): Không có ràng buộc gì thêm.

Cho một cây vô hướng gồm \(N\) đỉnh, đánh số từ \(1\) tới \(N\). Mỗi đỉnh \(i\) có một giá trị nguyên \(a_i\).
Ta gọi một tập đỉnh là hợp lệ nếu không có hai đỉnh nào trong tập kề nhau trên cây. Giá trị của một tập hợp lệ là tổng các giá trị \(a_i\) của những đỉnh được chọn.
Có \(Q\) thao tác online thuộc một trong hai loại sau:

• 1 x y: gán \(a_x = y\);
• 2 u v: xét đường đi đơn từ \(u\) tới \(v\), hãy tìm giá trị lớn nhất của một tập đỉnh hợp lệ nằm hoàn toàn trên đường đi đó.
  Hãy in ra đáp án cho mỗi truy vấn loại 2. Tập rỗng được xem là hợp lệ.

Input

• Dòng đầu tiên chứa hai số nguyên \(N,Q\). \((1 \le N,Q \le 2 \times 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\). \((-10^9 \le a_i \le 10^9)\)
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) mô tả một cạnh của cây. \((1 \le u,v \le N)\)
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác thuộc một trong hai dạng đã mô tả.

Output

• Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất là giá trị lớn nhất có thể thu được.

Example

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

9
7

7 8
5 -2 7 3 4 -1 6
1 2
1 3
2 4
2 5
3 6
6 7
2 4 7
1 2 10
2 4 5
1 6 20
2 7 5
1 5 -100
2 4 5
2 1 7

16
10
30
10
25

Scoring

• Subtask \(1\) \((20\%\) điểm\()\): \(N,Q \le 2000\).
• Subtask \(2\) \((20\%\) điểm\()\): Cây là một đường thẳng.
• Subtask \(3\) \((20\%\) điểm\()\): Không có thao tác loại 1.
• Subtask \(4\) \((40\%\) điểm\()\): Không có ràng buộc thêm.

Một đêm mưa lớn kéo qua khu rừng cổ, làm hệ thống đèn hiệu dẫn đường bị tắt gần hết, khiến PhuocThien và uou không thể tìm được lối đi an toàn giữa các trạm quan sát. Theo bản đồ cũ của khu rừng, có \(n\) trạm được nối với nhau bằng \(n - 1\) con đường hai chiều và toàn bộ mạng lưới tạo thành một cây. Trạm số \(1\) là trạm trung tâm, nơi lưu trữ nguồn năng lượng chính để khởi động lại hệ thống. Mỗi trạm \(i\) có hai giá trị đi kèm là năng lượng \(a_i\) và độ tin cậy \(c_i\). Nếu một trạm được chọn để kích hoạt, nó sẽ đóng góp đúng \(a_i\) điểm năng lượng cho hệ thống. Tuy nhiên, không phải trạm nào cũng có thể được chọn một cách độc lập, vì mọi trạm được chọn phải tạo thành một tập hợp liên thông và bắt buộc phải chứa trạm \(1\). Ngoài ra, để tránh làm quá tải mạng lưới, tổng độ tin cậy của các trạm được chọn không được vượt quá \(m\). PhuocThien muốn chọn đúng \(k\) trạm sao cho tập được chọn vừa liên thông, vừa chứa trạm \(1\), vừa có tổng độ tin cậy không vượt quá giới hạn, và tổng năng lượng thu được là lớn nhất có thể. Nếu có nhiều cách chọn hợp lệ, chỉ cần in ra giá trị lớn nhất của tổng năng lượng. Nếu không tồn tại cách chọn nào thỏa mãn, hãy in ra -1. uou còn nhắc rằng những trạm ở xa trạm trung tâm vẫn có thể được chọn, nhưng chỉ khi toàn bộ các trạm nằm trên đường đi từ trạm đó về trạm \(1\) cũng đều được chọn. Điều đó làm cho bài toán trở nên đặc biệt vì không phải cứ chọn các trạm có giá trị lớn nhất là đủ. Một số trạm có thể mang năng lượng âm, nên việc chọn thêm một trạm không phải lúc nào cũng có lợi. Có thể có những trường hợp giới hạn độ tin cậy khiến việc chọn đủ \(k\) trạm trở nên rất khó, thậm chí không thể thực hiện được. Hãy giúp PhuocThien khởi động lại chiếc đèn hiệu cuối cùng của khu rừng cổ.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(k\), \(m\) (\(1 \le k \le n \le 2500, 1 \le m \le 2500\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)), lần lượt là năng lượng của các trạm.
• Dòng thứ ba chứa \(n\) số nguyên \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 1000\)), lần lượt là độ tin cậy của các trạm.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\), \(u \ne v\)), mô tả một con đường hai chiều giữa hai trạm.
• Dữ liệu đảm bảo các con đường tạo thành một cây liên thông.

Output

• In ra một số nguyên duy nhất là tổng năng lượng lớn nhất có thể đạt được khi chọn đúng \(k\) trạm thỏa mãn mọi điều kiện.
• Nếu không tồn tại cách chọn hợp lệ, in ra -1.

Example

7 4 10
5 3 7 2 6 4 8
2 3 2 1 4 2 1
1 2
1 3
2 4
2 5
3 6
3 7

24

5 4 3
10 20 30 40 50
2 2 2 2 2
1 2
1 3
3 4
3 5

-1

Scoring

• Subtask \(1\) (\(20\) điểm): \(1 \le n \le 20\), \(1 \le k \le n\), \(1 \le m \le 20\).
• Subtask \(2\) (\(30\) điểm): \(1 \le n \le 200\), \(1 \le k \le 50\), \(1 \le m \le 200\).
• Subtask \(3\) (\(50\) điểm): Không có ràng buộc gì thêm.