앱 설치하기

산드라는 최근 첫 스마트폰을 샀다. 친구 한 명이 스마트폰에 설치하면 좋을 애플리케이션(앱) 목록을 길게 적어 주었다. 산드라는 곧바로 목록의 앱을 설치하기 시작했지만, 몇 개를 설치하고 나니 저장 공간이 부족해서 더는 설치할 수 없었다. 설치 패키지를 내려받을 공간조차 없어서 설치에 실패하는 앱도 있었고, 내려받기는 되지만 설치된 앱을 저장할 공간이 모자라는 앱도 있었다.

각 앱에는 다운로드 크기 $d$와 저장 크기 $s$가 있다. 앱을 내려받으려면 스마트폰에 최소 $d$메가바이트의 빈 공간이 있어야 한다. 설치가 끝난 앱은 스마트폰에서 $s$메가바이트를 차지한다. 앱 데이터가 강하게 압축된 경우처럼 다운로드 크기가 저장 크기보다 작을 수도 있고, 다른 언어 번역처럼 쓰이지 않을 자료가 다운로드에 포함된 경우처럼 더 클 수도 있다. 설치 프로그램은 매우 효율적이어서 내려받은 패키지를 추가 공간 없이 설치된 앱으로 바꾼다. 따라서 앱 하나를 설치하려면 스마트폰에 최소 $\max(d, s)$메가바이트의 빈 공간이 있어야 한다.

산드라는 앱을 잘못된 순서로 설치했기 때문에 공간이 부족해졌을지도 모른다는 사실을 곧 깨달았다. 그래서 앱을 모두 지우고 다시 설치하기로 했다. 이번에는 목록에서 가장 많은 앱을 설치할 수 있는 설치 순서를 고른다. 같은 앱을 두 번 이상 설치할 수는 없다.

목록의 어떤 앱을 어떤 순서로 설치해야 하는지 구하는 프로그램을 작성하시오.

입력은 다음과 같이 구성된다.

• 첫 줄에 정수 $n$과 $c$ ($1 \le n \le 500$, $1 \le c \le 10000$)가 주어진다. 각각 설치할 수 있는 앱의 수와 스마트폰의 빈 저장 공간(메가바이트)이다.
• 다음 $n$개 줄에 정수 $d$와 $s$ ($1 \le d, s \le 10000$)가 한 줄에 하나씩 주어진다. 각각 그 앱의 다운로드 크기와 저장 크기(메가바이트)이다.

첫 줄에 설치할 수 있는 앱의 최대 개수 $k$를 출력한다. $k$가 1 이상이면 둘째 줄에 그 $k$개 앱의 번호를 산드라가 설치해야 하는 순서대로 공백 하나로 구분해 출력한다. 설치할 수 있는 앱이 하나도 없으면 첫 줄만 출력한다.

앱 번호는 입력에 주어진 순서대로 1부터 $n$까지이다. $k$개를 설치할 수 있는 앱 집합이 여러 개일 수 있으므로 정답은 다음과 같이 하나로 정한다. 어떤 순서로든 설치할 수 있는 $k$개짜리 앱 집합 가운데, 앱 번호를 오름차순으로 나열했을 때 사전순으로 가장 앞서는 집합을 고른다. 두 수열은 처음으로 달라지는 위치의 수가 작은 쪽이 사전순으로 앞선다. 고른 집합의 앱을 $\max(d, s) - s$가 큰 것부터 내림차순으로 출력하고, 이 값이 같은 앱끼리는 번호가 작은 것을 먼저 출력한다. 어떤 순서로든 설치할 수 있는 집합은 이 순서로도 설치할 수 있으므로 이 순서는 항상 유효하다.