After the "Ladder Competition" (天梯赛), a company's human resources department requested a list of outstanding student recommendations from the organizing committee. This task was assigned to "Jingjing-jie" (静静姐).

The company's recommendation process follows these criteria:

• Only students scoring 175 or above in the Ladder Competition are considered.
• The company accepts recommendations in up to K batches.
• With in a single batch, students' Ladder Competition scores should ideally be strictly increasing.
• An exception is made: if a student's Ladder Competition score is the same as the previous student's, but this student has participated in the PAT exam and achieved the company's interview threshold score, they can still be accepted.

Given the Ladder Competition scores and PAT exam scores of all participating students, calculate the maximum number of students Jingjing-jie can recommend to the company.

Input Format

The first line contains three positive integers: N (≤ 105) for the total number of participating students, K (≤ 5×103) for the maximum number of recommendation batches, and S (≤ 100) for the company's PAT interview threshold score.

The following N lines each contain two scores: first, the student's Ladder Competition score (maximum 290), and second, their PAT exam score (maximum 100).

Output Format

Output a single integer representing the maximum number of students that can be recommended.

Sample Input

10 2 90
203 0
169 91
175 88
175 0
175 90
189 0
189 0
189 95
189 89
256 100

Sample Output

8

Explanation of Sample Output

In the first batch, we can select one student for each of the scores 175, 189, 203, and 256. Additionally, a student with a score of 175 who also achieved a PAT score of 90, and a student with a score of 189 who achieved a PAT score of 95, can be additionally included. For the second batch, only one student each with scores of 175 and 189 remains eligible. In total, 8 students are recommended.

Note: If a student's Ladder Competition score exceeds 175 and their PAT score meets the threshold, they are eligible for recommendation. For instance, a single batch could accommodate multiple students scoring 176 with passing PAT scores.

Code Implementation

The following C++ code calculates the maximum number of recommended students:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, k, s_threshold;
    std::cin >> n >> k >> s_threshold;

    // Arrays to store counts of students:
    // gplt_counts[score] = number of students with this Ladder Competition score
    // pat_qualified_counts[score] = number of students with this Ladder Competition score AND passing PAT score
    std::vector<int> gplt_counts(301, 0);
    std::vector<int> pat_qualified_counts(301, 0);

    for (int i = 0; i < n; ++i) {
        int ladder_score, pat_score;
        std::cin >> ladder_score >> pat_score;

        if (ladder_score >= 175) {
            gplt_counts[ladder_score]++;
            if (pat_score >= s_threshold) {
                pat_qualified_counts[ladder_score]++;
            }
        }
    }

    int total_recommendations = 0;

    // Iterate through possible Ladder Competition scores from 175 upwards
    for (int score = 175; score <= 300; ++score) {
        // First, add students who meet the PAT score requirement.
        // These students can be added regardless of batch constraints up to K.
        // The logic here implies each such student can be considered an 'extra' slot.
        total_recommendations += pat_qualified_counts[score];

        // Calculate remaining students for this score after PAT qualifiers are counted.
        int remaining_students = gplt_counts[score] - pat_qualified_counts[score];

        // Add as many of the remaining students as possible, up to K per batch.
        // Since each score can potentially be a new strictly increasing step,
        // we can add up to K students for this score if there are enough.
        total_recommendations += std::min(remaining_students, k);
    }

    std::cout << total_recommendations << std::endl;

    return 0;
}

The logic iterates through scores starting from 175. For each score, it first counts students who meet the PAT threshold, as these are considered special cases. Then, it counts the remaining students with that Ladder score. The total recommendations are accumulated by adding the PAT-qualified students and then the minimum of the remaining students and the batch limit k. This aproach correctly maximizes recommendations by prioritizing PAT qualifiers and then filling batches with other eligible students. The code uses vectors for dynamic sizing and std::min for clarity in calculating the number of students added per score.