AT_past17_h 履修登録

There are $ N $ courses in a university. The $ i $ -th course requires an effort of $ a_i $ , is scheduled at the $ b_i $ -th time slot, and counts for $ c_i $ credits. You need to take some of the courses to earn a total of $ M $ credits. However, you cannot take multiple courses scheduled at the same time slot. If you can earn $ M $ or more credits, print the minimum total effort required to do so; otherwise, print `-1`.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ \vdots $ $ a_N $ $ b_N $ $ c_N $

If you can earn $ M $ or more credits, print the minimum total effort required to do so; otherwise, print `-1`.

### Sample Explanation 1 If you take the $ 1 $ -st and $ 3 $ -rd courses, the total effort required is $ 8 $ , which is the minimum. Note that you cannot take both the $ 1 $ -st and $ 2 $ -nd courses, because they are scheduled at the same slot. ### Sample Explanation 2 Even if you take all the courses, you cannot earn $ 100 $ or more credits. ### Sample Explanation 3 The two courses are scheduled at the same time slot, so you cannot earn $ 100 $ or more credits. ### Constraints - $ 1 \leq N, M \leq 5000 $ - $ 1 \leq a_i,b_i,c_i \leq 5000 $ - All input values are integers.