5506: 强化(power)

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

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

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

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

接下来n行，每行五个正整数m_{i1}​、p_{i1}​、m_{i2}、p_{i2}​、k_i​，分别表示分解获得的金币数量、碎片数量，强化需要的金币数量、碎片数量以及强化获得的战斗力。

5
1 1 2 3 5
1 1 1 1 2
2 3 1 1 4
5 5 2 2 4
1 1 3 3 3

11