탐사대 식량

면접 대비

시간 제한1초메모리 제한1024 MB

요약

일행 c명이 하루에 c개씩 먹을 때, 각 음식 종류를 기한 t_i일 안에 모두 먹을 수 있는 종류의 최대 개수를 고릅니다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 힙
정답자: 아직 제출이 없습니다

문제

과학자들은 화성 탐사대의 식량을 계획하고 있다. 식량은 $n$ 가지 종류로 이루어져 있고, 각 종류에는 1부터 $n$ 까지 번호가 붙어 있다. 종류 $i$ 의 식량은 $k_i$ 인분이 있으며, 탐사를 시작한 뒤 $t_i$ 일 안에 먹어야 한다. $t_i$ 일이 지나고도 남은 종류 $i$ 의 식량은 모두 폐기된다.

탐사대는 $c$ 명이다. 매일 대원들은 가진 인분 중 $c$ 인분을 골라 먹는다. 대원들은 같은 종류를 먹을 수도 있고, 서로 다른 종류를 먹을 수도 있다.

계획 부서는 이 식량 계획에 여유가 얼마나 있는지 알고 싶어 한다. 어느 종류의 식량도 한 인분 폐기되지 않도록 탐사 중에 완전히 먹을 수 있는 식량 종류의 최대 개수를 구하라.

입력

첫 줄에 두 정수 $n$ 과 $c$ 가 주어진다 ( $1 \leq n \leq 2 \cdot 10^5$ , $1 \leq c \leq 10^9$ ). 이어지는 $n$ 개의 줄에는 각각 두 정수 $t_i$ 와 $k_i$ 가 주어진다 ( $1 \leq t_i \leq 10^9$ , $1 \leq k_i \leq 10^{18}$ ).

출력

첫 줄에 정수 $s$ ( $0 \leq s \leq n$ )를 출력한다. 이는 완전히 먹을 수 있는 식량 종류의 최대 개수이다. 다음 줄에는 종류의 번호 $p_1, p_2, \ldots, p_s$ ( $1 \leq p_i \leq n$ ) 를 출력한다. 번호는 모두 달라야 한다. 최대 크기의 집합이 여러 개라면 그중 아무것이나 출력해도 된다. 번호의 순서는 자유롭다.

예제3

예제 1
입력
```
1 1
4 4
```
예상 출력
```
1
1
```
예제 2
입력
```
5 3
3 4
2 6
4 5
3 4
5 7
```
예상 출력
```
3
1 4 5
```
예제 3
입력
```
3 2
2 6
4 9
1 3
```
예상 출력
```
0
```