题目描述

江桥准备购买一批花朵来丰富他的花园。

花卉市场里有 $n$ 朵花，这些花可以分为 $k$ 个种类。每朵花都有一个价值 $a_i$，一个价格 $b_i$，还有所属种类 $c_i$。

江桥还剩下 $w$ 的零花钱，他希望用这些钱购买总价值至少为 $v$ 的花朵，当然，这些钱可能不会全部花完。

为了保证花园的丰富性，他还希望每个种类的花朵都至少购买一朵。

由于买太贵的花可能会被扣零花钱，江桥希望在满足上述条件的情况下，使得所购买的花朵中最贵的花朵的价格尽可能小。

江桥请你来帮他计算一下，他的所有满足条件的购买方案中，所购买的花朵中最贵的花朵的价格最小是多少。

输入格式

第一行包含一行四个正整数 $n,k,w,v$，表示花朵数量、花朵种类数、零花钱数、总价值的期望值。

接下来 $n$ 行，每行三个正整数 $a_i,b_i,c_i$，表示第 $i$ 朵花的价值、价格和所属种类。

输出格式

一个整数，表示满足江桥条件下所购买的花朵中最贵的花朵的价格最小值。如果不存在满足条件的购买方案，输出 -1。

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

4

3 2 10 15
4 3 1
7 5 2
6 4 2 

-1

样例解释

第一组样例中，江桥可以购买第一朵花和第三朵花，花费 $3 + 4 = 7 < 10$ 元，总价值为 $4 + 6 = 10 \geq 10$，该方案中最贵的花为第三朵，因此答案为 $4$。

第二组样例中，在只有 $10$ 的零花钱下，无法达成购买的花朵总价值达到或超过 $15$，因此答案不存在。

数据规模与约定

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^3,1 \leq c_i \leq k \leq n,1 \leq w,b_i \leq 10^9,1 \leq v,a_i \leq 10^4$。