Mirror IIOT 2022-2023, International Round | binge

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 $M$ 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 $N$ shows that she wants to watch, in order. Every TV series is composed of $E_i$ episodes each with a length of $L_i$ minutes (where $i=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 $D$ Penny needs to watch all the TV series she has planned so far? How many minutes $S$ 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 $M$ and $N$. The following $N$ lines contain each two integers $E_i$ and $L_i$.

Output data

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

Constraints and Clarifications

• $1 \le M \le 1 \ 000 \ 000 \ 000$;
• $1 \le N \le 10 \ 000$;
• $1 \le E_i \le 1 \ 000 \ 000 \ 000$ for each $i=0\ldots N-1$;
• $1 \le L_i \le M$ for each $i=0\ldots N-1$.

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 \times 6 = 18$ minutes. With the remaining $42$ 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 $18$ 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 $15$ minutes. The other $45$ 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.