binge

Time limit: 0.2s Memory limit: 256MB Input: Output:

Penny spends too much time every day binge watching her favourite TV series! In order to get out of her addiction, she decided to be more disciplined and devote no more than MM minutes every day to her favourite activity.

To get the most out of the time that she has, Penny made a list of the next NN shows that she wants to watch, in order. Every TV series is composed of EiE_i episodes each with a length of LiL_i minutes (where i=0N1i=0 \ldots N-1). Penny will never start a TV series before finishing to watch the previous one; and will never start an episode in a day if she does not have enough time left to finish it. How many days DD Penny needs to watch all the TV series she has planned so far? How many minutes SS will Penny spare in the last day, that could be used to start watching a new TV series?

Input data

The first line contains the two integers MM and NN. The following NN lines contain each two integers EiE_i and LiL_i.

Output data

You need to write a single line with two integers DD and SS: the number of days needed to watch all the shows, and the number of minutes spared in the last day.

Constraints and Clarifications

  • 1M1 000 000 0001 \le M \le 1 \ 000 \ 000 \ 000;
  • 1N10 0001 \le N \le 10 \ 000;
  • 1Ei1 000 000 0001 \le E_i \le 1 \ 000 \ 000 \ 000 for each i=0N1i=0\ldots N-1;
  • 1LiM1 \le L_i \le M for each i=0N1i=0\ldots N-1.
# Score Restrictions
1 0 Examples.
2 10 Li=ML_i = M for each ii.
3 20 N=1N = 1.
4 30 Ei=1E_i = 1 for each ii.
5 40 No additional limitations.

Example 1

stdin

60 4
4 60
3 6
5 42
2 15

stdout

10 45

Explanation

Penny wants to spend an hour every day on TV series. Her first 4 days are spent watching the episodes of the first series. She can then watch the whole second series on the 5th day, using a total of 3×6=183 \times 6 = 18 minutes. With the remaining 4242 minutes she can already start the first episode of the third series on the 5th day, watching the following ones on days 6, 7, 8 and 9.

Notice that during days 6, 7 and 8, several minutes are left that cannot be used, since Penny does not want to start a new series before finishing the previous one. Part of the 1818 minutes left on the 9th day can however be used to start the last TV series. Her plan ends on the 10th day, with the only remaining episode of 1515 minutes. The other 4545 minutes are spare and usable for future shows.

Example 2

stdin

30 5
1000000000 30
1000000000 30
1000000000 30
1000000000 30
1000000000 30

stdout

5000000000 0

Explanation

Penny only wants to spend half an hour every day, forcing her to spend 5 billion days to end all the five TV series.

Log in or sign up to be able to send submissions!