Bài tập

Tại vùng ngoại ô rừng sâu, lễ hội ánh sáng ở thị trấn Aurora đang diễn ra --- một sự kiện chỉ xảy ra mỗi 10 năm một lần. Hana, một cô gái trẻ đầy tò mò, quyết định đi bộ xuyên rừng từ ngôi làng nơi cô sống (tọa độ \(x = 0\)) đến Aurora, cách đó \(X\) mét.

Cô bắt đầu hành trình với năng lượng ban đầu là \(D\). Để tiếp tục di chuyển, cô cần tiêu tốn đúng 1 đơn vị năng lượng cho mỗi mét đi bộ. Nếu năng lượng của cô giảm xuống dưới \(0\) tại bất kỳ thời điểm nào, Hana sẽ kiệt sức và không thể tiếp tục hành trình.

May mắn thay, dọc đường có \(n\) trạm tiếp sức, mỗi trạm cung cấp cho cô một ít thực phẩm hoặc nước giúp hồi phục năng lượng. Trạm thứ \(i\) nằm tại vị trí \(x_i\) trên tuyến đường và nếu dừng lại tại đó, Hana sẽ nhận thêm \(y_i\) đơn vị năng lượng. Mỗi trạm chỉ có thể sử dụng đúng một lần.

Hana muốn biết: tối thiểu cô cần dừng lại ở bao nhiêu trạm tiếp sức để có thể chắc chắn đến được Aurora mà không bao giờ cạn kiệt năng lượng.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(D\), \(X\) \((1 \leq n \leq 2 \cdot 10^5,\ 1 \leq D, X \leq 10^9)\) --- số lượng trạm tiếp sức, năng lượng ban đầu, và khoảng cách từ làng đến Aurora.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\) \((1 \leq x_i < X)\) --- vị trí của các trạm tiếp sức.
• Dòng thứ ba chứa \(n\) số nguyên \(y_1, y_2, \dots, y_n\) \((1 \leq y_i \leq 10^9)\) --- năng lượng nhận được tại mỗi trạm tương ứng.

Output

• In ra một số nguyên duy nhất --- số trạm tiếp sức tối thiểu mà Hana cần dừng lại để đến được Aurora. Nếu không có cách nào để đến nơi, in ra -1.

Example

5 5 12
3 4 7 8 11
3 2 1 2 1

3

5 10 40
1 20 30 2 38
7 7 7 7 7

5

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 30 & \(y_i = y_j\) với mọi \(i, j\)

2 & 30 & \(n \leq 1000\)

3 & 40 & Không có ràng buộc bổ sung

\hline
\endtabular

Trên trục số, có \(N\) đoạn thẳng. Đoạn thẳng thứ \(i\) có hai đầu nằm tại các điểm nguyên \(L_i\) và \(R_i\) \((0 \leq L_i \leq R_i \leq 10^9)\).

Bạn được phép chọn hai điểm nguyên \(x\) và \(y\) trên trục số (hai điểm này có thể trùng nhau). Một đoạn thẳng được gọi là được chọn nếu nó chứa ít nhất một trong hai điểm \(x\) hoặc \(y\).

Hãy tìm ra số đoạn được chọn lớn nhất trong tất cả các trường hợp của \(x\) và \(y\).

Input

• Dòng đầu tiên chứa một số nguyên \(N\) \((1 \leq N \leq 10^5)\) --- số đoạn thẳng.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(L_i\) và \(R_i\) --- biểu diễn đoạn thẳng thứ \(i\) \((0 \leq L_i \leq R_i \leq 10^9)\).

Output

• Ghi ra một số nguyên duy nhất --- số lượng đoạn thẳng được chọn nhiều nhất có thể.

Example

5
1 2
2 3
3 4
4 5
5 6

4

Scoring

• Subtask 1 (30 điểm): \(N \leq 100\), \(0 \leq L_i, R_i \leq 100\)
• Subtask 2 (20 điểm): \(N \leq 100\)
• Subtask 3 (20 điểm): \(N \leq 1000\)
• Subtask 4 (30 điểm): Không có ràng buộc bổ sung

Cho \(n\) điểm nguyên trên mặt phẳng tọa độ hai chiều.

Có \(q\) truy vấn dạng \((x, y, d)\). Mỗi truy vấn xác định một tam giác vuông cân có ba đỉnh là

Hãy đếm số lượng điểm trong \(n\) điểm đã cho nằm bên trong hoặc trên cạnh của tam giác này.

\InputFile
Dòng đầu tiên gồm hai số nguyên \(n, q\).

\(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(x, y\) mô tả một điểm \((x,y)\).

\(q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(x, y, d\) mô tả một truy vấn.

\OutputFile
In ra \(q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Điều kiện

• \(1 \le n, q \le 10^5\).
• \(1 \le x, y \le 10^5\) đối với các điểm.
• \(1 \le x, y, d \le 10^5\) đối với truy vấn.

Example

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

0
2

Cây là một đơn đồ thị vô hướng liên thông không có chu trình. Giữa hai đỉnh \(x\), \(y\) trên cây, luôn luôn tồn tại và duy nhất một đường đi đơn giữa chúng.

Cho một cây với các cạnh có trọng số không âm. Ta gọi khoảng cách giữa hai đỉnh là tổng xor (hay tổng nim) của các trọng số các cạnh trên đường đi đơn giữa hai đỉnh đó. Lưu ý là cặp \((x, y)\) và \((y, x)\) được coi là một cặp

Yêu cầu: Hãy tính tổng khoảng cách của tất cả các cặp đỉnh trên cây.

Input

• Dòng đầu ghi số nút của cây: \(n\)

• \(n - 1\) dòng tiếp theo, mỗi dòng ghi một cạnh của cây: \(u, v, L (1 ≤ u, v ≤ n)\)

Output

In ra một số nguyên là kết quả bài toán

Example

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

34

Scoring

• Trong tất cả các test: \(1 ≤ n ≤ 10^5 , 0 ≤ L ≤ 10^9\)

• Có \(20\%\) số test với \(n ≤ 5000\)

• Có \(30\%\) số test với mỗi đỉnh đều kề với nhiều nhất 2 đỉnh khác

• Có \(50\%\) số test với ràng buộc gốc