In the "Bao Le Me" food delivery system, there are N restaurents numbeerd from 1 to N. Each restaurant has a priority value that starts at 0 at time 0.

For every time unit:

• If a restaurant receives no orders, its priority decreases by 1, but never goes below 0.
• If it receives one or more orders, its priority increases by 2 per order.

A restaurant is added to the priority cache if its priority exceeds 5. It is removed from the cache if its priority drops to 3 or lower.

Given M orders occurring at various times up to time T, determine how many restaurants are in the priority cache exactly at time T.

Input Format

The first line contains three integers: N, M, and T.

The next M lines each contain two integers: ts (time stamp) and id (restaurant ID), indicating an order was placed at time ts for restaurant id.

Output Format

Output a single integer: the number of restaurants in the priority cache at time T.

Sample Enput

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

Sample Output

1

Approach

A brute-force simulation over all time steps and restaurants may exceed memory or time limits for large inputs (N, M, T ≤ 1e5). Instead, we process only the timestamps where orders occur, and simulate priority changes between those events.

Key ideas:

• Sort all orders by time (and by ID for grouping).
• For each restaurant, track:
  • Current priority score.
  • Last time it received an order.
• When processing an order at time t for restaurant id:
  • Decrement priority based on idle time since last order: score[id] -= (t - last[id] - 1).
  • Clamp score to ≥ 0.
  • Remove from cache if score ≤ 3.
  • Add 2 × order_count to priority.
  • Add to cache if score > 5.
  • Update last[id] = t.
• After processing all orders, simulate the final idle period from last order time to T for each restaurant.

Optimized Implementation

import java.util.*;

class Order {
    int time;
    int shopId;
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int t = sc.nextInt();

        Order[] orders = new Order[m];
        for (int i = 0; i < m; i++) {
            orders[i] = new Order();
            orders[i].time = sc.nextInt();
            orders[i].shopId = sc.nextInt();
        }

        Arrays.sort(orders, (a, b) -> {
            if (a.time != b.time) return a.time - b.time;
            return a.shopId - b.shopId;
        });

        int[] priority = new int[n + 1];
        int[] lastOrderTime = new int[n + 1];
        boolean[] inCache = new boolean[n + 1];

        int i = 0;
        while (i < m) {
            int currentTime = orders[i].time;
            int currentShop = orders[i].shopId;

            // Count all orders for this (time, shop)
            int count = 0;
            int j = i;
            while (j < m && orders[j].time == currentTime && orders[j].shopId == currentShop) {
                count++;
                j++;
            }

            // Simulate idle time since last order
            int idle = currentTime - lastOrderTime[currentShop] - 1;
            if (idle > 0) {
                priority[currentShop] = Math.max(0, priority[currentShop] - idle);
            }

            // Remove from cache if needed
            if (inCache[currentShop] && priority[currentShop] <= 3) {
                inCache[currentShop] = false;
            }

            // Apply new orders
            priority[currentShop] += 2 * count;

            // Add to cache if qualified
            if (!inCache[currentShop] && priority[currentShop] > 5) {
                inCache[currentShop] = true;
            }

            lastOrderTime[currentShop] = currentTime;
            i = j;
        }

        // Final simulation from last order to time T
        for (int shop = 1; shop <= n; shop++) {
            if (lastOrderTime[shop] < t) {
                int idle = t - lastOrderTime[shop];
                priority[shop] = Math.max(0, priority[shop] - idle);
                if (inCache[shop] && priority[shop] <= 3) {
                    inCache[shop] = false;
                }
            }
        }

        int result = 0;
        for (int shop = 1; shop <= n; shop++) {
            if (inCache[shop]) result++;
        }
        System.out.println(result);
    }
}