Cho \(N\) vật thể được đánh số từ \(1\) đến \(N\). Mỗi vật thể \(i\) có ba thông số:

• Trọng lượng \(w_i\)
• Thể tích \(a_i\)
• Giá trị \(v_i\)

Bạn có một cái túi có sức chứa tối đa về trọng lượng là \(W\) và sức chứa tối đa về thể tích là \(A\).

Hãy chọn một tập hợp các vật thể sao cho:

1. Tổng trọng lượng các vật thể được chọn không vượt quá \(W\).
2. Tổng thể tích các vật thể được chọn không vượt quá \(A\).
3. Tổng giá trị các vật thể được chọn là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(A\) (\(1 \le N \le 300\), \(0 \le A \le 300\)).
• Dòng thứ hai chứa số nguyên \(W\) (\(1 \le W \le 10^9\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(w_i, a_i, v_i\) (\(1 \le w_i \le 10^9\), \(0 \le a_i \le 300\), \(1 \le v_i \le 10\)).

Output

• In ra một số nguyên duy nhất là tổng giá trị lớn nhất đạt được.

Example

4 10
15
10 5 4
6 4 3
5 3 2
4 2 3

8

Scoring

• Subtask 1 (100 điểm): Không có ràng buộc gì thêm.