Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3049
Diablo II Items

Time Limit: 1 Second      Memory Limit: 32768 KB

Diablo II is the most famous ARPG (Act Role Playing Game) game in the world developped by Blizzard company. Diablo III is coming soon and Cannon group is reviewing Diablo II these days.

In Diablo II, there are generally two kinds of items: normal items and magic items. Normal items have no magic power, while the magic items has some magic power. Each normal item has an price P for selling, but each magic item has two prices for selling: the price before identify P1 and the price after identify P2 (Of cource, P2 is always larger than P1).

To identify an magic item, you should buy an identify scroll and use it to identify the magic item. After identify an magic item, the identify scroll will disappear. Each identify scroll will cost you Pi, and you can not by an identify scroll if you have no enough money.

Now you are in a town and you have many items, some are normal items and some are magic items. You know all the prices for the items and want to sell all of them. So what is the maximum amount of money you can earn?

You can assume:

  • You have no money at first.
  • All the magic items are not identified at first.
  • You can buy as many identify scrolls as possible, as long as you have enough money.


There are multiple test cases. There are two parts for each case. The first part is one line with two integer N and Pi (0 <= N, Pi <= 1000), the number of items you have and the price of an identify scroll. The second part consists with N lines. Each line gives the price (prices) for an item. For a normal item, the line will contain only a positive integer P (0 < P <= 10000). For a magic item, the line will contain two positive integers P1 and P2 (0 < P1 < P2 <= 10000).


For each case, print a number in one line, the maximum amount of money you can earn.

Sample Input

2 10
2 10
20 100

Sample Output


Author: HANG, Hang
Source: ZOJ Monthly, October 2008
Submit    Status