题目描述

小明现在有 $n$ 个 朋友，给他们编号 $1$ 到 $n$。请朋友吃饭是要花钱的，我们假设请 $i$ 号 朋友 吃饭要花 $rmb[i]$ 块大洋。而希望朋友成为自己 好朋友 是要费人品的，我们假设请第 $i$ 号朋友吃饭试图让她当自己 好朋友 的行为要耗费 $rp[i]$ 的人品。而对于每一个 朋友 来说，小明 都有一个对应的搞定她的时间，对于第 $i$ 个 朋友 来说叫做 $time[i]$。小明 保证自己有足够的魅力用 $time[i]$ 的时间搞定第 $i$ 个 朋友 ^_^。

小明 希望搞到尽量多的 朋友 当自己的 好朋友，这点是毋庸置疑的。但他不希望为此花费太多的时间，所以他希望在保证获得到 朋友 数量最多的情况下花费的总时间最少。

小明 现在有 $m$ 块大洋,他也通过一段时间的努力攒到了 $r$ 的人品（这次为模拟赛出题也攒 rp 哦~~）。他凭借这些大洋和人品可以泡到一些 朋友。他想知道，自己泡到最多的 朋友 花费的最少时间是多少。

注意 小明 在一个时刻只能去泡一个 朋友 ——如果同时泡两个或以上的 朋友 的话，她们会打起来的…

输入格式

输入的第一行是 $n$，表示 小明 看中的 朋友 数量。

接下来有 $n$ 行，依次表示编号为 $1, 2, 3, \ldots , n$ 的一个 朋友 的信息。每行表示一个 朋友 的信息，有三个整数：$rmb$，$rp$ 和 $time$。

最后一行有两个整数，分别为 $m$ 和 $r$。

输出格式

你只需要输出一行，其中有一个整数，表示 小明 在保证 朋友 数量的情况下花费的最少总时间是多少。

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

13

【数据规模】

对于 $20 \%$ 的数据，$1 \le n \le 10$； 对于 $100 \%$ 的数据，$1 \le rmb \le 100$，$1 \le rp \le 100$，$1 \le time \le 1000$。 对于 $100 \%$ 的数据，$1 \le m, r, n \le 100$。