P2967 [USACO09DEC] Video Game Troubles G

Farmer John's cows love their video games! FJ noticed that after playing these games that his cows produced much more milk than usual, surely because contented cows make more milk. The cows disagree, though, on which is the best game console. One cow wanted to buy the Xbox 360 to play Halo 3; another wanted to buy the Nintendo Wii to play Super Smash Brothers Brawl; a third wanted to play Metal Gear Solid 4 on the PlayStation 3. FJ wants to purchase the set of game consoles (no more than one each) and games (no more than one each -- and within the constraints of a given budget) that helps his cows produce the most milk and thus nourish the most children. FJ researched N (1

\* Line 1: Two space-separated integers: N and V \* Lines 2..N+1: Line i+1 describes the price of and the games available for console i; it contains: P\_i, G\_i, and G\_i pairs of space-separated integers GP\_j, PV\_j

\* Line 1: The maximum production value that Farmer John can get with his budget.