背景

20180209
SBW接到了SYF制作的最新MC地图《温柔乡》
在这个地图中玩家有两个能力“温”与“柔”
玩家可以通过做任务刷副本等操作积累能力
游戏目标是运用这两种能力打出招式以打败灾害性大魔王解放温柔乡
现在SBW已经积累了一定的能力并学会了一些招式打法
SBW想知道他最多能对大魔王造成多少伤害
为什么不帮帮SBW呢

描述

给出招式个数N，SBW“温”能力值\(M_1\)，SBW“柔”能力值\(M_2\)
每种招式需要损耗“温”能力c1，(或/并)损耗“柔”能力c2，并打出一些伤害val
(有的招type=1同时损耗两种能力，有的type=0可选一种损耗)
所有招式只能打一次，不然会被大魔王轻松躲过
求SBW最多打出多少伤害ans

输入

第一行三个整数N,\(M_1\),\(M_2\)
第二行至第N+1行
每行四个整数type, c1, c2, val

输出

一行一个整数ans

样例

输入

4 8 1
1 8 1 10
0 7 1 5
0 1 8 5
0 1 1 2

输出

12

范围

50% N,\(M_1\),\(M_2\)<=10 val<=1000
100% N,\(M_1\),\(M_2\)<=100 val<=100000 c1<=\(M_1\) c2<=\(M_2\) 0<=type<=1

限制

1s 128M