LXY 由于某次比赛未能出席,让 HYR 和 CGY 去死亡 2V3,躺在床上拿了一次银奖的关系,要请 HYR 和 CGY 吃饭。如今一行人来到了北京,人生地不熟选了一家酒店吃饭。正所谓见者有份,LXY 准备通过本次买单以还清 HYR 和 CGY 的恩情,但是 Dr.Su 却决定如果本次订单金额大于 ,就由他来代出。LXY 是个吃货,他想尽量的多吃东西,而且不让苏博士来买单,于是他决定把钱用在刀刃上。
已知每道菜的价格为 ,满足感为 ,一道菜最多可以点 次( 表示可以点无限次)。LXY 希望点单的价格不超过 的同时使得满足感最大。
LXY 虽然这样想,但是无奈数学太差,于是他找到了你,希望你帮他写一个程序算一下他最多能有多满足。
输入
第一行输入 分别表示有多少种食物和 Dr.Su 将会买单的价格。
接下来 行,每行输入三个正整数 ,分别表示第 道食物的价格,满足感和可以点的次数( 表示可以点无限次)。
输出
输出 LXY 可获得的最大的满足感。
样例
标准输入 复制文本 |
3 10 2 1 0 3 3 1 4 5 4 |
标准输出 复制文本 |
11 |
提示
第一种食物点 份,第三种食物点 份。
总价格为 。
最大满足感为 。
来源
2018 软件学院蓝桥杯热身赛 (For 16/17)