XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: fotografia.x, onde x deve ser c, cpp, java, js ou py

Fotografia

Chegou o final do ano, e os alunos resolveram dar um presente para a profa. Vilma: um quadro com a fotografia dos alunos classe. João está pesquisando os preços de molduras em um site da internet, e precisa de sua ajuda. Ele quer encontrar uma moldura tal que

  • a fotografia seja inteiramente contida dentro na moldura; e
  • a área da moldura não ocupada pela fotografia seja a menor possível; e
  • uma moldura pode ser rotacionada para acomodar a fotografia, mas a fotografia deve ser acomodada de forma que seus lados sejam paralelos aos lados da moldura.

Dada as dimensões da fotografia e das molduras disponíveis, escreva um programa para ajudar João a escolher a melhor moldura, segundo os critérios acima.

Entrada

A primeira linha da entrada contém dois inteiros A e L indicando respectivamente a altura e largura da fotografia, em centímetros. A segunda linha da entrada contém um inteiro N, a quantidade de molduras disponíveis. As molduras são identificadas por números de 1 a N. Cada uma das N linhas seguintes contém dois inteiros Xi e Yi indicando as dimensões em centímetros da moldura de número i, para 1 ≤ i ≤ N.

Saída

Seu programa deve produzir uma única linha na saída, contendo um único número inteiro, o identificador da melhor moldura de acordo com os critérios acima. Se houver mais de uma moldura que satisfaz os critérios, o programa deve produzir o menor identificador entre as mulduras que satisfazem os critérios. Se nenhuma moldura satisfaz os critérios, a linha deve conter -1.

Restrições

  • 1 ≤ A ≤ 100
  • 1 ≤ L ≤ 100
  • 1 ≤ N ≤ 100
  • 1 ≤ Xi ≤ 200 para 1 ≤ i ≤ N
  • 1 ≤ Yi ≤ 200 para 1 ≤ i ≤ N
  • não há duas molduras com as mesmas dimensões

Exemplos

Entrada
10 20
3
20 20
25 10
5 5
Saída
2
	

 

Entrada
24 30
1
25 25
Saída
-1
	

 

Entrada
20 20
4
30 30
30 10
35 40
25 36
Saída
1
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação