小慕手头有一笔资金（m万元）准备进行投资，他调研了多种（n种）理财产品，并分析了每种产品的和风险等级（记为r，用1-10表示，数值越大风险越高）。小慕所在团队的风控规定，投资产品的风险等级不能超过x，且单个产品的投资金额不能超过y元。请帮小慕规划一个满足风控要求、能获得最大预期收益的投资方案，并输出该方案的预期收益。
提示：带虚线的词点一下有通俗解释。
输入描述
输入的第一行为可用于投资的金额m（万元），调研的投资产品种类数n（种），风险部门要求的最高可以投资风险等级x。单个产品的最大投资金额y（万元），用空格分割； 第二行开始为每个产品的预期收益率e（%）和每个产品的风险等级r，用空格分割。 不考虑非法输入，所有输入都是正整数，输出结果四舍五入取整，输入输出均小于2^31
输出描述
输出计算的最大预期收益
示例
示例 1
输入
100 7 5 10 10 3 15 5 14 3 20 7 18 6 17 4 30 9
输出
6
时间限制 1000 ms · 内存限制 128 MB