Các bãi cỏ ở Иннополис được cắt bằng những robot cắt cỏ chạy điện. Ta coi bãi cỏ là một đoạn trên trục số, với các robot cắt cỏ nằm tại một số điểm trên đoạn đó. Có thể bỏ qua kích thước của các robot. Một robot đứng ở đầu bãi cỏ (bên trái nó không có bãi cỏ), và một robot đứng ở cuối bãi cỏ (bên phải nó không có bãi cỏ). Ban đầu, mỗi robot hướng về một trong hai phía: sang phải hoặc sang trái.
Lượng điện của robot thứ $i$ đủ để xử lý $p_i$ mét bãi cỏ. Sau khi sạc qua đêm, tất cả robot bắt đầu làm việc đồng thời và di chuyển với cùng tốc độ. Mỗi robot di chuyển theo hướng của mình dọc theo trục số. Robot dừng lại trong một trong ba trường hợp:
- Robot hết điện. Nói cách khác, robot thứ $i$ đã đi được $p_i$ mét từ vị trí xuất phát.
- Robot đã đến đầu hoặc cuối bãi cỏ.
- Robot gặp tại cùng một điểm một robot khác đang đi ngược chiều với nó hoặc đã dừng tại điểm đó trước đó.
Trước khi khởi động các robot, bạn có thể đổi hướng của một số robot sang hướng ngược lại. Cần cắt hết cỏ trên toàn bộ bãi cỏ.
Hãy xác định số robot ít nhất cần đổi hướng để cuối cùng toàn bộ cỏ trên bãi cỏ được cắt. Nếu không thể, hãy thông báo rằng không thể cắt hết cỏ.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 10^5$) — số robot.
$n$ dòng tiếp theo mô tả các robot theo thứ tự vị trí của chúng trên trục số từ trái sang phải. Mỗi robot được mô tả bằng ba số nguyên $x_i,p_i,d_i$: vị trí ban đầu, số mét nó có thể di chuyển và hướng di chuyển ($0=x_1<x_2<\cdots<x_n \le 10^9$, $1 \le p_i \le 10^9$; giá trị $d_i=-1$ biểu thị di chuyển sang trái, theo chiều giảm tọa độ, còn $d_i=1$ biểu thị di chuyển sang phải, theo chiều tăng tọa độ). Đầu và cuối bãi cỏ lần lượt nằm tại $x_1=0$ và $x_n$.
Dữ liệu ra
Trên một dòng duy nhất, in ra $-1$ nếu không thể cắt hết cỏ trên bãi cỏ. Nếu không, in ra một số — số robot cần đổi hướng sang hướng ngược lại để bãi cỏ được cắt hết.
Nhiệm vụ con
| Nhiệm vụ con | Điểm | Giới hạn về $n$ | Giới hạn bổ sung | Nhiệm vụ con cần thiết |
|---|---|---|---|---|
| 1 | 23 | $n \le 10$ | Ví dụ | |
| 2 | 16 | Ban đầu tất cả robot đều hướng sang phải ($d_i=1$) | ||
| 3 | 17 | $n \le 1000$ | Ví dụ, 1 | |
| 4 | 13 | $x_i=i-1$, $p_i=1$ | ||
| 5 | 14 | $p_i=10^9$ | ||
| 6 | 17 | Không có giới hạn bổ sung | Ví dụ, 1–5 |
Ví dụ
Dữ liệu vào 1
3 0 1 -1 1 1 1 2 1 -1
Dữ liệu ra 1
1
Dữ liệu vào 2
2 0 1 1 4 2 -1
Dữ liệu ra 2
-1
Ghi chú
Ví dụ đầu tiên được minh họa trong hình. Để cắt hết cỏ, chẳng hạn, có thể quay robot ở giữa sang hướng ngược lại.