oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

potions Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

potions.html

Problem Description

Admist the current chaos in the Maple World, x3JiaYin the Mercedes is preparing for her epic battle against the Black Mage. However, even though she has Elven Healing, which utilizes energy purified by nature to continously recover HP and MP, this amount is insufficent as it only regenerates 5% of x3JiaYin's MaxHP and MaxMP per 4 second.

As such, she decides to bring along some potions in order to replenish her HP and MP in the battle against the Black Mage. Sadly, after paying 10m for the Unicorn Special Meal required to feed her dear Charlie the Unicorn, x3JiaYin is only left with M mesos (the currency that Maple World uses).

Walking along Elluel, she met Erwin, the Merchant who specializes in selling potions. Erwin has T different types of potions in stock of different quantities. Each potion recovers a certain amount of HP and/or MP but some positive amount of mesos are required to purchase it.

Each potion can be described with the following attributes:

  • HP Recovered - The amount of HP this potion will recover if it was utilized.
  • MP Recovered - The amount of MP this potion will recover if it was utilized.
  • Price - The price of purchasing this potion, in mesos.

In order to optimize the amount of HP and MP the potions she buys will recover, she has enlisted for your help. Given the list, description and amount of potions Erwin sells, determine the maximum amount of HP and MP regeneration x3JiaYin can recover from the potions purchased from Erwin using less than M mesos in total.

HP and MP regeneration is defined as sum of the total number of HP recovered and MP recovered of all the potions.

Input

The first line of input consists of 2 integers, M followed by T.

Subsequently, T lines of input will each consist of 4 integers each, with the ith line consisting of HPi, MPi, Ci and Ai, representative of the attributes that describe potion i: HP Recovered, MP Recovered, Price for a single potion and quantity of the potion Erwin has in stock.

Output

A single integer, denoting the maximum HP and MP regeneration that can be obtained through the purchase of potions.

Limits

0 ≤ T ≤ 100

0 ≤ M ≤ 1000000

0 ≤ Ai ≤ 10000

0 ≤ HPi, MPi ≤ 30000

M % 100 = 0

Ci % 100 = 0

Subtasks

  • Subtask 1 (10%): T≤1
  • Subtask 2 (10%): T≤2
  • Subtask 3 (20%): Ai = 1
  • Subtask 4 (30%): Ai≤10
  • Subtask 5 (30%): Refer to Limits.

Sample Input 1

10000 1
500 500 1000 7

Sample Output 1

7000

Sample Input 2

10000 2
250 500 500 15
500 0 500 10

Sample Output 2

13750

Sample Input 3

10000 5
50 0 100 10000
100 100 200 10000
200 100 200 10000
500 400 700 10000
1000 0 900 10000

Sample Output 3

15000

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11010.3s512MBMinimum
21010.3s512MBMinimum
32020.3s512MBMinimum
43030.3s512MBMinimum
53030.3s512MBMinimum
6030.3s512MBMinimum

Judge Compile Command

g++-8 ans.cpp -o potions -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.