MOG Round #2Ended |
Fito es famoso porque tiene un algoritmo para coger dinero matando bichos en el bosque, él siempre sabe si puede matar a los bichos a los que se enfrenta. Para esto él tiene que saber acerca de él y de cada bicho del bosque el daño y la vida que tienen.
El daño de un bicho o de un héroe es la cantidad de vida que le quita a un enemigo cuando le da un golpe .
La vida de un bicho determina cuántos golpes hay que darle para que muera. Por ejemplo si Fito tiene daño 50 (le resta al enemigo 50 de vida con cada golpe), y se enfrenta a un bicho que tiene 110 de vida, el tendrá que darle 3 golpes para poder matarlo.
Cuando Fito se enfrenta a un grupo de bichos comienza a darle golpes a alguno de ellos, y todos los bichos empiezan a darle golpes a él.
Se sabe que Fito al igual que los bichos da 1 golpe por segundo, y que cada golpe va dirigido a un solo bicho. Por ejemplo si Fito se enfrenta a 3 bichos, en el primer segundo el escoge darle un golpe a alguno de los bichos y recibe un golpe de cada bicho.
Por ejemplo, si hay dos bichos, uno con 100 de vida y 30 de daño, otro con 50 de vida y 5 de daño, y su héroe tiene 80 de vida y 50 de daño, entonces Fito mata al de 100 de vida y 30 de daño en 2 golpes primero y luego al de 50 de vida en un tercer golpe. Recibe un total de daño de 75 por lo cual termina con 5 de vida.
En caso de que matara primero al de 50 de vida y luego al de 100 recibiría un total de 95 de daño por lo cual moriría antes de matarlos ya que solo tiene 80 de vida. Ahí está la habilidad de Fito que el siempre encuentra la mejor manera de matarlos y sabe si puede o no.
Como tú quieres jugar tan bien como juega Fito , te interesa hacer lo mismo que él, o sea, saber si con la vida que tiene tu héroe y el daño que hace por golpes puedes matar a los bichos del bosque. Si puedes además te interesa saber cuál es la mayor cantidad de vida con la que te puedes quedar.
Un entero positivo $z \leq 10$ con la cantidad de casos.
Por cada caso:
En la primera línea habrá dos enteros $1 \leq a,b \leq 10^{18}$ que representan la vida y daño de tu héroe respectivamente.
En la segunda línea habrá un entero $1 \leq n \leq 10^4$ que es la cantidad de bichos del bosque.
A continuación habrá $n$ líneas con dos enteros $1 \leq c,d \leq 10^5$ con la vida y el daño respectivamente de los bichos del bosque.
Escriba la vida con la mayor cantidad de vida con la que se puede quedar tu héroe en caso de que se pueda, y “NO” en caso contrario. Si Fito y el último bicho se mueren al mismo tiempo, la respuesta es "NO"