题目内容

商城双$11$大促销，每种商品限购两件。一共有$M$种商品。每种商品的原始价格为$X$元。买一件折扣价是$Y$元，买两件折扣价是$Z$元。其中$X>=Y>=Z$。小明银行卡里有余额$N$元。在$N$元的范围内怎么购买商品，才可以获得最多的优惠金额?

输入描述

第$1$行:商品种类$M$，$M$的范围是$[1,20]$。

第$2$到$M+1$行:每个商品的原始价格$X$元，购买一件的折扣价$Y$元，购买两件的折扣价$Z$元。 X\Y\Z的范围是$[1,1000]$。

第$M+2$行:小明银行卡余额$N$元。N的范围是$[1,20000]$，$N$元至少可以购买一件商品。

输出描述

输出可以获得的最多优惠金额

样例1

输入

2
10 8 6
8 6 6
20

输出

10

说明

第一个商品买$2$件，第二个商品买$1$件。总共花费$2^*6+6=18$元在$20$元范围内。

第一件商品优惠$8$元($2$件)，第二件商品优惠$2$元($1$件)。总共优惠$10$元。

样例2

输入

3
10 8 4
20 17 13
30 20 10
50

输出

55

说明

第一个商品买$2$件，第二个商品买$1$件第三个商品买$2$件。总共花费$2^*4+17+2^*10=41$元在$50$元范围内。

第一件商品优惠$12$元($2$件)，第二件商品优惠$3$元($1$件)，第三件商品优惠$40$元($2$件)，总共优惠$55$元。