• Todos os tipos de bactérias à venda terão o mesmo preço.
• Todas as bactérias (de todos os tipos) se subdividem todas as noites para gerar outras bactérias. Por exemplo, a bactéria da colônia de tipo X se subdivide em 2 outras bactérias todas as noites. Assim, no primeiro dia teremos só uma bactéria na colônia. No dia seguinte, teremos 2, e no próximo, 4. A quantidade de divisões de uma bactéria depende do seu tipo.
• O crescimento da colônia cessa após um determinado número de dias, por causa da escassez de alimento. A quantidade de dias em que uma colônia cresce depende do tipo de bactéria.

É final de mês e Bruno já gastou quase todo o seu dinheiro. Assim, resolveu que irá comprar apenas uma colônia de bactérias. No entanto, ele pretende comprar a colônia que forneça a maior quantidade de bactérias ao final do período de crescimento da mesma.

Ele tem um catálogo mostrando os tipos de bactérias à venda. Para cada tipo de bactéria, o catálogo informa a quantidade de bactérias geradas por uma bactéria desse tipo a cada divisão e por quantos dias a população da colônia crescerá. Porém, a calculadora que ele tem em casa não é suficiente para que ele faça os cálculos necessários para decidir qual é a melhor colônia a comprar.

Tarefa

Bruno pediu sua ajuda para decidir qual é o melhor tipo de bactéria para a compra. Lembre que para Bruno o melhor tipo de bactéria é aquele cuja colônia, ao final do período de crescimento, terá a maior quantidade de bactérias.

Você deve supor que não haverá duas colônias com a mesma população final de bactérias.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 50.000) representando a quantidade tipos de bactérias no catálogo. Cada uma das N linhas seguintes contém informações sobre um tipo de bactéria: a primeira dessas linhas contém a informação da bactéria de tipo 0, a segunda dessas linhas contém a informação sobre a bactéria de tipo 1, e assim por diante. A última dessas linhas contém a informação da bactéria de tipo N - 1.

A informação para cada tipo de bactéria é composta por dois números inteiros D e C (1 ≤ D ≤ 2.000 e 1 ≤ C ≤ 5.000), onde D é quantidade de bactérias que cada bactéria deste tipo gera ao se dividir numa noite, e C é a quantidade de dias que a população de bactérias crescerá.

Saída

Seu programa deve imprimir, na saída padrão, um número inteiro entre 0 e N - 1 representando o tipo da bactéria que Bruno deverá comprar.

Informações sobre a pontuação

• Em um conjunto de casos de teste que totaliza 20 pontos, N ≤ 1.000, D^C ≤ 1.000.000.
• Em um conjunto de casos de teste que totaliza 80 pontos, N ≤ 2.000, D ≤ 2.000, C ≤ 5.000.

Exemplos

4
145 15
2 4999
3 3211
135 20			

2			

2
2 5
3 4

1

5
2 1
4 5
30 4
20 6
2 154

4