Installing Apps

Sandra recently bought her first smartphone. A friend gave her a long list of applications (apps) that she should install on it. Sandra started installing the apps from the list right away, but after a few installs the phone no longer had enough disk space for any more. Sometimes an installation failed because there was not even enough space to download the installation package. Other apps downloaded fine but then had too little space to store the installed app.

Each app has a download size $d$ and a storage size $s$. To download the app, the phone needs at least $d$ megabytes of free disk space. Once the app is installed, it occupies $s$ megabytes of disk space on the phone. The download size can be smaller than the storage size (for example, when the app data is heavily compressed) or larger than the storage size (for example, when the download carries material that may never be used, such as translations into other languages). The installer is very efficient and turns the downloaded package into an installed app without using any extra disk space. So, to install an app, the phone needs at least $\max(d, s)$ megabytes of free disk space.

Sandra soon realised that she may have run out of space only because she installed the apps in the wrong order. She uninstalled every app and now wants to pick an installation order that lets her install as many apps from the list as possible. Sandra installs each app at most once.

Help her decide which apps on the list to install, and in which order.

The input consists of:

• One line with two integers $n$ and $c$ ($1 \le n \le 500$, $1 \le c \le 10000$), the number of available apps and the free disk space of the phone in megabytes.
• $n$ lines, each with two integers $d$ and $s$ ($1 \le d, s \le 10000$), the download size and the storage size of an app, in megabytes.

On the first line, print the maximum number $k$ of apps that can be installed. If $k$ is at least 1, print a second line with the numbers of those $k$ apps, separated by single spaces, in the order Sandra should install them. If no app can be installed, print only the first line.

The apps are numbered from 1 to $n$ in input order. Several sets of $k$ apps may be installable, so the accepted answer is fixed as follows. Among all sets of $k$ apps that can be installed in some order, choose the set whose app numbers, written in increasing order, form the lexicographically smallest sequence. Of two sequences, the one with the smaller number at the first position where they differ is lexicographically smaller. Print that set sorted by $\max(d, s) - s$ in decreasing order, and by app number in increasing order among apps with the same value of $\max(d, s) - s$. Any set that can be installed in some order can also be installed in this order, so the printed order is always valid.