Problem A - Blocks are falling

Blocks are vertically falling... some stay over the floor; others stay over previous blocks, depending on their horizontal position and dimensions. All blocks are one unit height and maintain their horizontal position and orientation.

Figure 1 presents an example. The identifier of a block is related to the order of falling: block 1 is the first to fall, block 2 is the second, and so on.

Figure 1
Figure 1: Example of 13 blocks falling

Since blocks 1 and 2 do not intersect, they stay over the floor or, in other terms, they stay on level 1; however, block 3 has to stay over the above, so it remains on level 2 and, when block 4 falls, it stays on level 3. Similar rules can be applied to the resting blocks.

The Problem

Given a sequence of falling blocks, the problem is to determine the maximum level attained and identify the correspondent blocks. In the example given, it can be seen that the result is 4, with blocks 8 and 11. Each block is described by its left coordinate x (any decimal value, positive or negative) and its length (any integer value larger than zero).


Input is given as a list of text lines, the first containing the number N of blocks for the problem.

It is followed by N lines containing a coordinate x (decimal value) and a length (integer value) separated by one or more spaces. Identifier of the corresponding block is implicit in these lines sequence (block 1, 2, etc.).

The number of blocks is limited to 1000. It is ensured that no coincidences can occur in coordinates x of right side and left side of contiguous blocks.


One text line containing the level result and another line containing the M number of blocks in that situation. These are followed by M lines containing the identifiers of the M blocks found in that level, in the order left to right.

Sample Input

1.048 1
4.091 3
-3.919 9
-2.984 1
6.054 2
9.031 4
3.09 1
1.047 3
10.038 7
7.097 6
7.014 6
15.078 1
18.03 1

Sample Output


Note: the sample input and output correspond to the example given in figure 1.

CPUP 2007
Universidade do Porto