LCC '22 Contest 2 J4 - Unbe-leaf-able Schedules

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

James is quite the unbe-leaf-able K-Pop idol. Not only is he extremely popular, he also has a special ability which allows him to perform in many locations at once.

James has just released a new album, and is now going on a world tour, which will last N days. Due to his popularity, he has been invited to perform an absurd number of times. Luckily for James, his special ability has come in handy.

However, even the most unbe-leaf-able idols have limits, and that includes James. He can only perform at up to M places at once. If he exceeds this amount, his performance quality would decrease drastically and James would like to prevent that at all costs.

If James is scheduled to perform Q times, with each show beginning at day A and ending at day B, can you help James determine if he can actually pull this schedule off?

Note: Python users are recommended to use PyPy 2/3 over Python 2/3 when submitting.

Constraints

1 \le A_i \le B_i \le N \le 10^7

1 \le M \le 10^5

1 \le Q \le 10^5

Input Specification

The first line will contain N, M and Q, each seperated by a space

The next Q lines will contain 2 space-seperated integers, A_i and B_i, representing the beginning and end days of the i^{th} show.

Output Specification

If James's schedule isn't possible to pull off, that is, if he has to perform at more than M locations at once, output TAKE A BREAK JAMES

Otherwise, output the highest number of simultaneous performances James has.

Sample Input 1

5 3 5
1 5
2 3
3 4
4 5
1 2

Sample Output 1

3

Comments

There are no comments at the moment.