Đề bài

Một sự kiện kéo dài N ngày.

Ban đầu số người tham gia trong mọi ngày đều bằng 0.

Có Q sự kiện cập nhật.

Mỗi sự kiện gồm ba số:

L R X

nghĩa là cộng thêm X người cho tất cả các ngày từ L đến R.

Sau khi thực hiện toàn bộ cập nhật, hãy tìm ngày đầu tiên có số người lớn hơn hoặc bằng C.

Nếu không có ngày nào thỏa mãn, in ra:

-1

Dữ liệu vào

Dòng đầu chứa ba số nguyên N, Q, C.

Q dòng tiếp theo chứa ba số nguyên L, R, X.

Dữ liệu ra

In ra ngày đầu tiên có số người ≥ C.

Giới hạn

1 ≤ N ≤ 10⁶
1 ≤ Q ≤ 2×10⁵
1 ≤ X ≤ 10⁹

Ví dụ

Input

7 3 10
1 4 3
3 6 5
5 7 4

Output

3

Giải thích

Ngày 3 có tổng số người là 8.
Ngày 4 có tổng số người là 8.
Ngày 5 có tổng số người là 9.
Sau khi cộng đủ dữ liệu, ngày đầu tiên đạt ngưỡng là ngày 3.