가속도 최대화

베시는 다가오는 그랑프리를 앞두고 레이스카를 손보고 있다. 현재 이 자동차의 질량은 $M$이고, 앞으로 나아가는 힘(추진력)은 $F$이다. 성능 부품 가게에서는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 부품을 판다. 각 부품은 가게에 한 개씩만 있으므로, 베시는 부품들의 임의의 부분집합을 (아무것도 사지 않는 경우 포함) 골라 장착할 수 있다.

$i$번 부품을 장착하면 자동차의 힘이 $F_i$만큼, 질량이 $M_i$만큼 늘어난다. 뉴턴의 제2법칙 $F = M \cdot A$에 따라, 자동차의 가속도는 전체 힘을 전체 질량으로 나눈 값과 같다. 베시가 부품 집합 $S$를 장착하면 가속도는 다음과 같다.

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

예를 들어 $F = 1500$, $M = 100$인 자동차에 힘이 $150$이고 질량이 $9$인 부품 하나를 장착하면, 가속도는 $15$에서 $(1500 + 150) / (100 + 9) \approx 15.14$로 커진다.

베시는 가속도를 최대로 만드는 부품 집합을 고르려고 한다. 서로 다른 여러 집합이 같은 최대 가속도를 낸다면, 그중 전체 질량이 가장 작은 집합을 선택한다. 이 두 규칙에 따르면 최적의 부품 집합은 유일하게 정해진다.

제약 조건

• $1 \le M \le 1000$
• $1 \le F \le 1{,}000{,}000$
• $1 \le N \le 20$
• $1 \le F_i \le 1{,}000{,}000$
• $1 \le M_i \le 1000$

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

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

베시가 장착해야 하는 부품들의 번호를 오름차순으로 한 줄에 하나씩 출력한다. 아무 부품도 장착하지 않아야 한다면 NONE을 출력한다.