Description

In the “Bao Le Me” takeaway system, there are $N$ takeaway shops, numbered from $1$ to $N$. Each shop has a priority value. Initially (at time $0$), all priorities are $0$.

For every $1$ unit of time:

• If a shop has no orders, its priority decreases by $1$, but not below $0$.
• If a shop has orders, its priority does not decrease. Instead, for each order, its priority increases by $2$.

If at some time a shop’s priority is greater than $5$, it will be added to the priority cache. If its priority is less than or equal to $3$, it will be removed from the priority cache.

Given $M$ order records within time $T$, compute how many shops are in the priority cache at time $T$.

Input Format

The first line contains $3$ integers $N$, $M$, and $T$.

The next $M$ lines each contain two integers $ts$ and $id$, meaning that at time $ts$, the shop with number $id$ received one order.

Output Format

Output one integer representing the answer.

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

1

Hint

Sample Explanation

At time $6$, shop $1$’s priority drops to $3$ and is removed from the priority cache; shop $2$’s priority increases to $6$ and is added to the priority cache. Therefore, there is $1$ shop (shop $2$) in the priority cache.

Constraints and Rules

For $80\%$ of the testdata, $1 \le N, M, T \le 10000$.

For all testdata, $1 \le N, M, T \le 10^5$, $1 \le ts \le T$, $1 \le id \le N$.

Lanqiao Cup 2019 Provincial Contest, Group A, Problem G.

Translated by ChatGPT 5