Food Supplies for the Expedition

Interview

Time limit1sMemory limit1024 MB

Summary

Pick the largest set of food types that can be fully eaten by their deadlines when c members eat c portions per day.

Level: Medium6 of 10
Topics: Greedy, Sorting, Heap
Solved: No attempts yet

Statement

Scientists are planning food supplies for an expedition to Mars. The supply has $n$ types of food, numbered from 1 to $n$ . Type $i$ has $k_i$ portions, and it must be eaten within $t_i$ days after the expedition starts. Any portions of type $i$ left after $t_i$ days are discarded.

The expedition has $c$ members. Each day, the members choose any $c$ portions they have and eat them. Members may eat the same types or different types.

The planning department wants to know how much spare food the plan has. Find the maximum number of food types that can be completely eaten during the expedition, with no portion of any type discarded.

Input

The first line contains two integers $n$ and $c$ ( $1 \leq n \leq 2 \cdot 10^5$ , $1 \leq c \leq 10^9$ ). Each of the next $n$ lines contains two integers $t_i$ and $k_i$ ( $1 \leq t_i \leq 10^9$ , $1 \leq k_i \leq 10^{18}$ ).

Output

First print the integer $s$ ( $0 \leq s \leq n$ ), the maximum number of food types that can be completely eaten. On the next line, print $s$ distinct integers $p_1, p_2, \ldots, p_s$ ( $1 \leq p_i \leq n$ ), the type numbers. If several sets of maximum size work, print any of them. The types may be printed in any order.

Examples3

Example 1
Input
```
1 1
4 4
```
Expected output
```
1
1
```
Example 2
Input
```
5 3
3 4
2 6
4 5
3 4
5 7
```
Expected output
```
3
1 4 5
```
Example 3
Input
```
3 2
2 6
4 9
1 3
```
Expected output
```
0
```