小李很喜欢玩氪金手游，不过他还是个学生，他的预算很有限，他准备用有限的预算尽可能强化他的手游卡牌。

在这个游戏内，对于一张卡牌，你可以选择分解或者强化，当你选择分解时，你可以获得m_1枚金币和p_1个碎片，不同的卡牌分解的金币和碎片数不同；当你选择强化时，你需要花费m_2枚金币和p_2个碎片，然后获得k的战斗力，不同的卡牌需要的金币、碎片以及强化后的战力也不同。

因为小李的预算很有限，且手游里保留某种卡牌没有意义。小李这次充值了一大笔钱，然后获得了一些卡牌，请你帮他计算出这些卡牌可以获得的最大战斗力。假设小李一开始的金币和碎片数量均为0。

输入的第一行包含以个正整数 n，表示卡牌的数量。

接下来n行，每行五个正整数m_i1 、p_i1 、m_i2 、p_i2 、k_i，分别表示分解获得的金币数量、碎片数量，强化需要的金币数量、碎片数量以及强化获得的战斗力。

输出一行仅一个数字，表示获得的最大战斗力。

【样例1解释】

小李一共有五张卡牌，各张卡牌的情况如下：

小李的最优解只有一种做法，选择分解第4张卡牌和第5张卡牌，一共获得5+1=6枚金币和5+1=6个碎片，选择强化第1、2、3张卡牌，分别需要2+1+1=4枚金币和3+1+1=5个碎片。获得战斗力5+2+4=11。

对于其他做法，比如分解第2张卡牌和第5张卡牌，虽然能获得5+4+4=13的战斗力，一共获得1+1=2枚金币和1+1=2个碎片，而强化需要2+1+2=5枚金币，需要3+1+2=6个碎片。强化需要的金币和碎片不够。

又比如分解第1、2、5张卡牌，可以获得1+1+1=3枚金币，1+1+1=3个碎片。强化第3、4张卡牌，需要1+2=3枚金币，1+2=3个碎片，强化需要的金币和碎片是足够的，但是只能获得4+4=8的战斗力。

【数据范围】

对于所有测试数据有：1≤n≤90,0≤m_i1 、p_i1 、m_i2 、p_i2≤10,0≤k_i≤10^6。

云南编程挑战赛