Wake up... I have to code...

Time limit2sMemory limit512 MB

Summary

Given N alarms that ring at T, T+K, T+2K, ..., pick two so their union of ring times up to D is largest, breaking ties lexicographically.

Level: Medium7 of 10
Topics: Math, Number theory, Brute force, Hash map
Solved: No attempts yet

Problem

Geonmo codes until dawn every day and goes to work early in the morning. To set an alarm quickly and get some sleep, he plans to turn on only two alarms. But in case he does not hear them, he wants to turn on the two alarms that can ring the most times by the time he has to wake up. Let us pick the alarms that Geonmo should turn on.

The alarm Geonmo uses has a snooze button. The snooze button turns off a ringing alarm and makes it ring again after a short while.

Geonmo presses the snooze button as soon as every alarm rings, until the time he has to wake up. If he keeps pressing snooze, two alarms sometimes ring at the same time. In that case the two alarms ring as one, and pressing the snooze button for either of them acts as if the snooze button were pressed for both alarms.

For example, suppose the list of alarms he can turn on is given as follows. The snooze time $K$ is the time from pressing the snooze button until the alarm rings again.

Alarm number	Start time $T$	Snooze time $K$	Description
1	0	2	The alarm rings at times 0, 2, 4, 6, $\ldots$
2	5	5	The alarm rings at times 5, 10, 15, 20, $\ldots$
3	6	3	The alarm rings at times 6, 9, 12, 15, $\ldots$
4	0	10000	The alarm rings at times 0, 10000, 20000, $\ldots$

If the time Geonmo has to wake up is $30$ , he can hear the alarms as follows.

Alarm number	Times the alarm rings	Total ring count
1	0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30	16
2	5, 10, 15, 20, 25	5
3	6, 9, 12, 15, 18, 21, 24, 27, 30	9
4	0	1

If he turns on alarms 1 and 3, the alarms ring twenty times as follows. An alarm ringing at times (6, 12, 18, 24, 30) is counted as ringing only once.

Each position with a red dot is a time the alarm rings.

He may choose other alarms, but no choice rings as many times or more.

Input

The first line gives two integers, the number of alarms $N$ and the time Geonmo has to wake up $D$ , separated by a space. $(2 \le N \le 1\,000$ , $1 \le D \le 10^9)$

From the second line, the $i$ -th of $N$ lines gives the start time of the alarm $T\_i$ and the snooze time $K\_i$ , separated by a space. $(0 \le T\_i \le D$ , $1 \le K\_i \le 10^9)$

All values in the input are integers, and for every $i$ , $T\_i$ is guaranteed to be a multiple of $K\_i$ .

Output

On the first line, print the two alarm numbers Geonmo should turn on in increasing order, separated by a space.

If there are several answers, print the lexicographically smallest one.

On the second line, print the number of times the alarms ring.

Examples2

Example 1
Input
```
4 30
0 2
5 5
6 3
0 10000
```
Expected output
```
1 3
20
```

Example 2

Input

Expected output

3 5
36