小红购买装备

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

题目描述

小红准备去打地下城，在进入地下城之前首先需要购买合适的装备。
已知商店共有 $n$ 件装备，每种装备提供 $a_i$ 的攻击和 $b_i$ 的防御，价格为 $c_i$ ，小红身上已有的装备攻击为 $x$ ，防御为 $y$ ，该装备卖给商店可以回收 $z$ 金币。另外小红拥有的金币数量为 $T$ 。
小红的战斗力计算为攻击+防御。现在小红想知道自己最终从装备处可以获得的战斗力最大值是多少？
注：小红最多只能生效一件装备！

输入描述:

第一行输入五个正整数，分别代表商店的装备数量、小红身上的装备攻击、防御、回收价格，以及小红携带的金币。
接下来的行，每行输入三个正整数，代表商店每件装备的攻击、防御和金币数量。

输出描述:

一个正整数，代表小红从装备处获得的最高战斗力。

示例1

输入

复制

2 100 30 50 100
120 50 120
200 100 1000

输出

复制

说明

小红卖掉身上的装备，购买第一件装备即可。