The problem involves selecting the maximum number of students for recommendation under specific constraints:

• Only students with a score of atleast 175 are eligible.
• Exactly K recommendation batches are allowed.
• Within each batch, student scores must be non-decreasing, and strictly increasing unless a student has a qualifying PAT score.
• Students with the same score as the previous one can still be included if their PAT score meets or exceeds a given threshold S.

To solve this efficiently, we avoid storing individual student records. Instead, we use two frequency arrays indexed by score (from 175 to 290):

• total[score]: total number of students with that score (≥175).
• qualified[score]: number of those students whose PAT score ≥ S.

For each of the K batches, we iterate through scores from 175 to 290. For each score:

1. If any students remain at this score, select one (this satisfies the strictly increasing requirement when moving to the next distinct score).
2. Then, while there are remaining students at this score who also have qualifying PAT scores, include them all in the current batch (since duplicates are allowed if PAT-qualified).

This greedy approach ensures maximal inclusion per batch with out violating ordering rules.

Python Implementation:

if __name__ == '__main__':
    n, k, pat_threshold = map(int, input().split())
    total = [0] * 291
    qualified = [0] * 291

    for _ in range(n):
        ladder, pat = map(int, input().split())
        if ladder >= 175:
            total[ladder] += 1
        if pat >= pat_threshold:
            qualified[ladder] += 1

    recommended = 0
    for _ in range(k):
        for score in range(175, 291):
            if total[score] > 0:
                recommended += 1
                total[score] -= 1
                while total[score] > 0 and qualified[score] > 0:
                    recommended += 1
                    total[score] -= 1
                    qualified[score] -= 1

    print(recommended)

C Implementation:

#include <stdio.h>

int main() {
    int n, k, s;
    scanf("%d %d %d", &n, &k, &s);

    int total[291] = {0};
    int qualified[291] = {0};

    for (int i = 0; i < n; i++) {
        int ladder, pat;
        scanf("%d %d", &ladder, &pat);
        if (ladder >= 175) total[ladder]++;
        if (pat >= s) qualified[ladder]++;
    }

    int count = 0;
    while (k--) {
        for (int score = 175; score <= 290; score++) {
            if (total[score] > 0) {
                count++;
                total[score]--;
                while (total[score] > 0 && qualified[score] > 0) {
                    count++;
                    total[score]--;
                    qualified[score]--;
                }
            }
        }
    }

    printf("%d\n", count);
    return 0;
}