Card Combination Count

You are given N cards, where the i-th card has an attack value A_i and a health value H_i. Your task is to select exactly K cards such that the total attack and total health values of the chosen cards meet or exceed given thresholds.

Formally, let the chosen set of cards be C with |C| = K. You need to ensure that:

$$\sum_{i \in C} A_i \geq P$$ $$\sum_{i \in C} H_i \geq Q$$

Count the number of ways to choose K cards that satisfy these conditions.

inputFormat

The input is given via stdin in the following format:

• The first line contains four space-separated integers: N (number of cards), K (cards to choose), P (minimum total attack), and Q (minimum total health).
• The next N lines each contain two space-separated integers, A_i and H_i, representing the attack and health values of the i-th card.

outputFormat

Output a single integer to stdout — the number of valid combinations of cards.

5 2 25 45
10 20
15 10
20 30
5 25
10 10

2