**1 人解决**，1 人已尝试。

**1 份提交通过**，共有 4 份提交。

**9.3** EMB 奖励。

**单点时限: **1.0 sec

**内存限制: **256 MB

Clash Royale is a real time strategy card game. Each card has an attack power and a level. Each player picks 8 cards to form a battle deck; the total attack power of a deck is the sum of the attack power of each of its cards. Players fight with each other by placing cards from their battle decks into the battle arena. The winner of a battle is rewarded with coins, which can be used to upgrade cards. Upgrading a card increases its attack power.

After days of arena fighting, Little Shawn has accumulated a total of coins. He has decided to upgrade some of his cards. Little Shawn has cards. The -th card can have any level from through ; the attack power for the -th level is . Cards must be upgraded one level at a time; the price to upgrade the -th card from level to level costs coins. The -th card is currently at level before Little Shawn has upgraded any cards.

Little Shawn wants to use some or all of his coins to upgrade cards, and then form a deck of exactly 8 cards, so that the deck’s total attack power is as large as possible. Can you help him do this? He can upgrade the same card more than once as long as he can afford it, and he does not have to upgrade every card.

The test case starts with 2 integers and , the number of coins and the number of cards that Little Shawn possesses. Then blocks follow. The -th block consists of 3 lines describing the -th card. The first line contains two integers and , the maximum possible level and current level of the card. The second line contains integers , the attack power of each level. The third line contains integers , the number of coins required to upgrade a card that is currently at level .

Output an answer, that is the maximal possible total attack power of a deck that Little Shawn can form, using the coins that he has.

Input

20 8 3 1 1 10 100 1 2 3 1 1 10 100 1 3 3 1 1 10 100 1 4 3 1 1 10 100 1 5 3 1 1 10 100 1 6 3 1 1 10 100 1 7 3 1 1 10 100 1 8 3 1 1 10 100 1 9

Output

422

Input

30 10 4 1 1 10 100 200 1 2 3 3 1 1 10 100 2 4 3 1 1 10 100 3 6 4 2 1 10 100 200 4 8 16 3 1 1 10 100 5 10 3 1 1 10 100 6 12 3 1 1 10 100 7 14 3 1 1 10 100 8 16 3 1 1 10 100 9 18 3 1 1 10 100 10 20

Output

504

In sample case #1, you can upgrade the first 4 cards to level 3, upgrade the 5th and 6th card to level 2, keep the last 2 cards level 1. This will cost you (1+2)+(1+3)+(1+4)+(1+5)+1+1=20 coins and the total attack power is 100+100+100+100+10+10+1+1=422 which is the maximal possible we can get.

Sample case #2 would only appear in Large dataset.

**1 人解决**，1 人已尝试。

**1 份提交通过**，共有 4 份提交。

**9.3** EMB 奖励。

题目标签