#P1509. 找啊找啊找GF

找啊找啊找GF

题目背景

“找啊找啊找 GF,找到一个好 GF,吃顿饭啊拉拉手,你是我的好 GF。再见。”

“诶,别再见啊…”

七夕… 七夕… 七夕这个日子,对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌,他还是很痛苦。为了避免这种痛苦,sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM,让她给自己一个出题的任务。经过几天的死缠烂打,zmc MM 终于同意了。

但是,拿到这个任务的 sqybi 发现,原来出题比单身更让人感到无聊 -_- … 所以,他决定了,要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。

题目描述

sqybi 现在看中了 nn 个 MM,我们不妨把她们编号 11nn。请 MM 吃饭是要花钱的,我们假设请 ii 号 MM 吃饭要花 rmb[i]rmb[i] 块大洋。而希望骗 MM 当自己 GF 是要费人品的,我们假设请第 ii 号 MM 吃饭试图让她当自己 GF 的行为(不妨称作泡该 MM)要耗费 rp[i]rp[i] 的人品。而对于每一个 MM 来说,sqybi 都有一个对应的搞定她的时间,对于第 ii 个 MM 来说叫做 time[i]time[i]。sqybi 保证自己有足够的魅力用 time[i]time[i] 的时间搞定第 ii 个 MM ^_^。

sqybi 希望搞到尽量多的 MM 当自己的 GF,这点是毋庸置疑的。但他不希望为此花费太多的时间(毕竟七夕赛的题目还没出),所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。

sqybi 现在有 mm 块大洋,他也通过一段时间的努力攒到了 rr 的人品(这次为模拟赛出题也攒 rp 哦~~)。他凭借这些大洋和人品可以泡到一些 MM。他想知道,自己泡到最多的 MM 花费的最少时间是多少。

注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话,她们会打起来的…

输入格式

输入的第一行是 nn,表示 sqybi 看中的 MM 数量。

接下来有 nn 行,依次表示编号为 1,2,3,,n1, 2, 3, \ldots , n 的一个 MM 的信息。每行表示一个 MM 的信息,有三个整数:rmbrmbrprptimetime

最后一行有两个整数,分别为 mmrr

输出格式

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

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

提示

sqybi 说:如果题目里说的都是真的就好了…

sqybi 还说,如果他没有能力泡到任何一个 MM,那么他就不消耗时间了(也就是消耗的时间为 00),他要用这些时间出七夕比赛的题来攒 rp…

【数据规模】

对于 20%20 \% 的数据,1n101 \le n \le 10
对于 100%100 \% 的数据,1rmb1001 \le rmb \le 1001rp1001 \le rp \le 1001time10001 \le time \le 1000
对于 100%100 \% 的数据,1m,r,n1001 \le m, r, n \le 100