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

题目描述

牛牛打 CF，已知一场比赛有 n 道题，第 i 道题的满分为 a_i，时间系数为 b_i，保底分为 c_i，本场比赛中每次错误提交罚 p 分。即如果牛牛在第 x 分钟，这道题 y 次错误提交后通过第 i 题，他将获得 max(c_i,a_i-x\times b_i-y\times p) 分。比赛持续 t 分钟，即在 t 分钟（含第 t 分钟）内做出的题目计入总分。你已经知道了他第 i 题需要花费的时间 x_i 和错误提交次数 y_i ，请求出牛牛可能的最大得分。

输入描述:

第一行三个正整数 n,t,p(1\le n\le9,1\le t,p\le10^9)。
接下来 n 行，每行 5 个正整数 a_i,b_i,c_i,x_i,y_i(0 \le a_i,b_i,c_i,x_i,y_i \le 10^9,c_i \le a_i)。

输出描述:

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

输入

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

输出

复制 
1266

说明

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

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

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

故可能的最大得分为 1266。