Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3718
Diablo II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.

Input

The first line contains two integers K(K≤7), N(0≤N≤100) which respresent for the number of skills and nubmer of amulets.

Then there contains K lines, the i-th line contains three integers bi, ci, di.(0<bi≤5,0≤ci, di≤1000)

Then there contains N lines, the i-th line describe the i-th amulet. In the i-th line, there first comes two integer ai and mi(0≤ai≤1000,0≤miK) while mi means the number of skills that are related with this amulet. Then there comes mi integers which are the order number of these related skills.

At last there is a line contains two integers X and Y.(0≤X≤35, 0≤Y≤ 100)

Output

Output a integer which respresents for the biggest power you can increase.

Sample Input

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

Sample Output

20

Author: ZHANG, Ruijie
Contest: ZOJ Monthly, June 2013
Submit    Status