## DMOPC '17 Contest 1 P4 - Quests

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 64M
Authors:

Problem type

In a distant kingdom, there lived a certain knight. What did this knight do? Play video games of course!

In his most recent video game, there are NPCs, each of whom offers a distinct repeatable quest. It takes the knight hours to reach the NPC and he gains gold along the way. Once he reaches an NPC, he can perform its quest as many times as he likes. Doing the quest takes him hours and rewards him with gold. This knight wishes to obtain as much gold as he can, however he cannot log more than hours, lest his lord find out and fire him. Can you help this knight find out the maximum amount of gold he can obtain?

#### Constraints

For all subtasks, , , and .

and for all

#### Input Specification

The first line of input will have two space separated integers, and .
The next lines of input will each have four space separated integers, , , , and in that order.

#### Output Specification

A single integer, the maximum amount of gold the knight can get after hours.

#### Sample Input 1

3 6
6 1 3 1
7 1 1 1
3 1 9 2

#### Sample Output 1

28

#### Explanation for Sample 1

The knight should go to the second NPC but not do its quest. Then, he should go to the third NPC and do its quest twice. This gives him gold and takes him hours.

#### Sample Input 2

5 7
8 2 10 2
9 1 7 1
1 2 8 1
5 3 2 1
7 1 4 3

#### Sample Output 2

51

#### Explanation for Sample 2

The knight should go to the second NPC and do its quest six times.

#### Sample Input 3

5 557
819777 142 467177 150
647198 31 265541 155
903546 115 261596 138
757957 84 108764 101
935057 137 532908 164

#### Sample Output 3

4063535