ZOJ Problem Set - 3718
Diablo II is a very interesting RPG(Role-Playing Game), it's famous for it's Equipment and Skill system. When the players are exploring the world, they may meet many monsters. The stronger a monsters is, the more experience and better equipments you will get after killing it. When a player gets enough experience, he will level up and get a skill-point which can make one skill level up if you add it on that skill. So with good arrangement of equipments and the way of adding skill-points, a player can make him much stronger. And it's easy to understanding why skills and equipments are so important to players
Edward is playing Diablo II, and he use his smart mind to create a way which is full of "science" to quantificat his role's power. Now Edward has saved X skill-points, and he has k skills. For the i-th skill, he can add at most bi skill-points on that skill which means he can make it level up for at most bi times. Every time you add one skill-point on the i-th skill, you can increase you power by ci. But if you add bi skill-points on the i-th skill, you make it get the full-level and you can additionally increase you power by di.
And Edward has collect N amulets while amulet is a kind of equipment that has amazing power. The i-th amulet has a power ai which means if you take the amulet with you, you can increase you power by ai. And Edward can take at most Y amulets with him.
Besides this some amulet may make some of your skill level up temporarily while we call the i-th amulet is related with these skills, it means when you take the amulet with you it has the same effect as if you add every skill the amulet is related with. For example if the first amulet is related with skill 1 and skill 3 while you add 1 skill-point to skill 1 and 4 skill-points to skill 3, when you take the first amulet with you the level of skill 1 is 2 and the level of skill 3 is 5. But if you take the first amulet off, the level of skill 1 and skill 3 will become 1 and 4 again. And you can get your power increased from skill if you make your skill level up by the amulet with you. But because of the rule of the games, one skill can be level up for at most once even if you have sevel different amulets that are related with the same skill. And the i-th skill's level can't be more than bi even with the help of amulets.
The first line contains two integers K(K≤7), N(0≤N≤100) which respresent for the number of skills and nubmer of amulets.
Output a integer which respresents for the biggest power you can increase.
5 4 4 3 2 5 1 8 5 1 10 5 1 12 5 1 14 4 1 2 3 1 3 2 1 4 1 1 5 4 1
Author: ZHANG, Ruijie
Contest: ZOJ Monthly, June 2013