Need For Speed

Bessie는 다가오는 그랑프리를 앞두고 경주용 자동차를 손보고 있으며, 더 빠르게 만들기 위해 추가 부품을 사려고 한다.

현재 이 자동차의 질량은 $M$ ($1 \le M \le 1000$)이고, 스스로를 앞으로 밀어내는 힘은 $F$ ($1 \le F \le 1{,}000{,}000$)이다. 뉴턴의 제2법칙에 따르면 $F = MA$이므로, 가속도는 $A = F / M$이다.

부품 상점에는 $1$번부터 $N$번까지 번호가 매겨진 $N$ ($1 \le N \le 10{,}000$)개의 부품이 있으며, 각 부품의 재고는 최대 한 개이다. $i$번 부품을 사면 힘이 $F_i$ ($1 \le F_i \le 1{,}000{,}000$)만큼, 질량이 $M_i$ ($1 \le M_i \le 1000$)만큼 늘어난다. Bessie는 부품의 어떤 부분집합이든 (하나도 사지 않는 경우 포함) 자유롭게 살 수 있다.

부품 집합 $S$를 장착하면 자동차의 총 힘은 $F + \sum_{i \in S} F_i$, 총 질량은 $M + \sum_{i \in S} M_i$가 되어 가속도는 다음과 같다.

$A = \frac{F + \sum_{i \in S} F_i}{M + \sum_{i \in S} M_i}$

이 가속도를 최대로 만드는 부품 집합을 고르시오. 최대 가속도가 같은 집합이 여러 개라면 총 질량이 가장 작은 집합을 고른다. 최적의 집합은 유일함이 보장된다.

예를 들어 힘이 $f$, 질량이 $m$인 부품 하나만 장착하면 가속도는 $(F + f) / (M + m)$으로 바뀐다.

첫째 줄에 세 정수 $F$, $M$, $N$이 공백으로 구분되어 주어진다.

다음 $N$개의 줄 중 $i+1$번째 줄에는 $i$번 부품이 더하는 힘과 질량을 나타내는 두 정수 $F_i$와 $M_i$가 공백으로 구분되어 주어진다.

Bessie가 장착해야 할 부품의 번호(1부터 시작)를 오름차순으로 한 줄에 하나씩 출력한다. 어떤 부품도 장착하지 않는 것이 최적이라면 NONE을 출력한다.