BSSPC '21 J4 - James's Magical Soups

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Python 3.0s
Memory limit: 256M

Author:
Problem types

James loves drinking soup, specifically, magical soup. However, being the connoisseur of soup that he is, he is a picky drinker — meaning that his soup must be up to his standards. In particular, every time he drinks soup, it must satisfy the following conditions:

  • The temperature of each bowl of soup must be no more than X when he drinks it, or his mouth will get burned. Each bowl of soup starts at some integer temperature T_i and cools down by 1 unit at the end of each minute.
  • Each bowl of soup must also be at most F_i minutes old when he drinks it. It isn't fresh enough for him after that.

James starts out with N bowls of fresh, new, zero-minute-old soup. Every minute, he can consume at most one bowl of soup. Can you find out the maximum amount of bowls of soup he can drink?

Constraints

For all subtasks:

0 \le X, N, T_i, F_i \le 500\,000

Subtask 1 [10%]

0\le X, N, T_i, F_i \le 100

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line will contain 2 integers X and N, representing James' temperature threshold and the number of bowls of soup.

The following N lines will each contain two integers T_i and F_i, denoting the starting temperature of each bowl of soup and the amount of time the soup must be consumed in.

Output Specification

Output one integer, the maximum number of bowls of soup James can drink.

Sample Input 1

1 3
3 2
5 1
2 3

Sample Output 1

2

Explanation for Sample Output 1

James can wait 1 minute to drink the third bowl of soup as the temperature of the soup cools down to 1. He can wait another minute to drink the first bowl. The second bowl will expire after 1 minute, but the bowl is still too hot so he cannot drink it.

Sample Input 2

20 5
100 91
30 10
69 10
20 1
1 2

Sample Output 2

4

Comments

There are no comments at the moment.