G-小白要写小白题_第五届SCPC中南民族大学程序设计竞赛（同步赛）（重现赛）@XuSihan

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

酱酱是队内知名小白，ta 参加了一场训练赛。

已知比赛有 $n$ 道题，第 $i$ 道题的满分为 $a_i$ ，时间常数为 $b_i$ ，至少能获得 $c_i$ 分，比赛中每次提交若不通过则扣 $p$ 分。即如果酱酱在第 $x$ 分钟，在 $y+1$ 次提交时正好通过第 $i$ 题（即有 $y$ 次提交不通过），ta 将获得 $max(c_i,a_i−x*b_i−y*p)$ 分。比赛持续 $t$ 分钟，即在 $t$ 分钟（含第 $t$ 分钟）内做出的题目计入总分。

你已经知道了酱酱第 $i$ 题需要花费的时间 $x_i$ 和错误提交次数 $y_i$ ，请求出酱酱可能的最大得分。

输入描述:

第一行三个整数 。

接下来  行，每行  个整数，同时 。

输出描述:

一行一个整数，表示可能的最大得分。

示例1

输入

复制

3 120 50
500 2 150 6 1
1000 4 300 12 2
1500 6 450 120 3

输出

复制

备注:

方案一：先开第 3 题，在 120 分钟时切掉，得到1500−120×6−50×3=630 分。此时已无法继续切题，总分 630。

方案二：先开第 1 题，在 6 分钟时切掉，得到 438 分。再开第 2 题，在 18 分钟时切掉，得到 828 分。无法切第三题，总分 1266。

方案三：先开第 2 题，在 12 分钟时切掉，得到 852 分。再开第 1 题，在 18 分钟时切掉，得到 414 分。无法切第三题，总分 1266。故可能的最大得分为 1266。