Songs

John Doe is a famous DJ and therefore faces the problem of optimizing how songs are placed on his tapes. For a given tape, and for each song on that tape, John knows the length of the song and how often it is played. His task is to record the songs on the tape in an order that minimizes the expected access time.

If the songs are recorded in the order $S_{s(1)}, \dots, S_{s(n)}$, then the quantity to minimize is

$\sum_{i=1}^{n} f_{s(i)} \sum_{j=1}^{i} l_{s(j)}$

where $f_{s(i)}$ is the playing frequency of the song placed $i$-th and $l_{s(j)}$ is the length of the song placed $j$-th. (The inner sum is the time needed to reach the $i$-th song: the total length of the songs recorded up to and including it.) Can you help John?

The input is read from a text file and consists of several data sets. A data set starts with the number $N$ (which fits in a 16-bit integer) of songs. Then follow the $N$ song specifications and, finally, a number giving the position of a song $S$ on the optimized tape. A song specification consists of the song identifier (an integer), the length of the song (which fits in a 16-bit integer), and the playing frequency of the song (a floating-point number). White space may occur freely in the input, which is always valid and terminates at end of file.

For each data set, print on its own line, starting at the beginning of the line, the identifier of the song that ends up at the requested position in an order minimizing the expected access time. If two songs have the same length-to-frequency ratio $l/f$, swapping them leaves the cost unchanged; in that case they are kept in the order they appear in the input, so the song at each position is uniquely determined.