F. Bribing Friends G

Bessie 想要观看纪录片：奶牛基因组学，但她不想一个人去。不幸的是，她的朋友们没有足够的热情和她一起去！于是，Bessie 需要贿赂她的朋友们陪她去电影院。她的贿赂武器库中有两种工具：哞尼和冰激凌甜筒。

Bessie 有 个朋友。然而，并非所有的朋友都是生而平等的！朋友 有受欢迎度 ，Bessie 想最大化陪她的朋友们的受欢迎度之和。朋友 只有当 Bessie 给了她 哞尼才愿意陪她。如果 Bessie 给她 个冰激凌甜筒，她还可以给 Bessie 哞尼的折扣。Bessie 可以从朋友那里得到任意整数数量的折扣，只要这些折扣不会使得朋友倒给她哞尼。

Bessie 有 哞尼和 个冰激凌甜筒可供使用（）。请帮助她求出如果她以最优方案花费她的哞尼和冰激凌甜筒，她可以达到的最大受欢迎度之和。

输入的第 1 行包含三个整数 ， 和 ，分别表示 Bessie 拥有的朋友的数量，哞尼的数量和冰激凌甜筒的数量。

以下 行每行包含三个整数 ， 和 ，表示受欢迎度（），贿赂朋友 陪 Bessie 所需要的哞尼（），以及从朋友 处获得 哞尼的折扣所需要的冰激凌甜筒的数量（）。

输出陪 Bessie 的朋友们的最大受欢迎度之和，假设她以最优方案花费她的哞尼和冰激凌甜筒。

样例输入 #1

3 10 8
5 5 4
6 7 3
10 6 3

样例输出 #1

15

样例 1 解释

Bessie 可以将 哞尼和 个冰激凌甜筒给奶牛 ，将 哞尼和 个冰激凌甜筒给奶牛 ，这样奶牛 和 就可以陪她，得到 的受欢迎度。

输入文件名为：bribing.in

输出文件名为：bribing.out

• 测试点 满足 以及 。
• 测试点 满足 。
• 测试点 满足 。
• 测试点 满足 。
• 测试点 没有额外限制。