Một ông chủ có \(m\) lò rèn và \(n\) thợ. Thợ thứ \(i\) sẵn sàng làm việc trong các ngày từ \(L_i\) đến \(R_i\), mỗi ngày làm việc, thợ sẽ sử dụng một lò rèn để đóng móng ngựa cho một con ngựa và yêu cầu giá tiền công một ngày là \(C_i\). Ông chủ muốn lên kế hoạch trong \(t\) ngày để tổng số con ngựa được đóng móng là nhiều nhất và tổng số tiền ít nhất có thể.

Input

• Dòng đầu chứa ba số nguyên \(n, m, t\) (\(n, m \le 200000; t \le 10^9\)).
• Tiếp theo là \(n\) dòng, mỗi dòng chứa ba số nguyên \(L_i, R_i, C_i\) (\(1 \le L_i \le R_i \le t, C_i \le 10^4\)).

Output

• Gồm một dòng chứa hai số là số con ngựa được đóng móng là nhiều nhất và tổng số tiền ít nhất có thể.

Example

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

9 15

Scoring

• Nguồn: 3D'21