G1024
题号：NC232587
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

期末考试结束后，图灵杯出题组的几位同学卑微地留在校出题，但是由于疫情影响，他们不得不尽快乘坐G1024号火车离开学校 ，现在假设图灵杯出题组共n人，并且通过APP可以知道G1024在接下来k天的已购票数x，总票数m，现在Phenix想知道在所有人都一起上火车的前提下最早在第几天可以离开学校，如果无论怎样都无法离开请输出“G!”

输入描述:

第一行两个整数n,k，表示出题组人数和天数
接下来k行,第i行两个整数x,m表示接下来第i天G1024的已购票数和总票数

输出描述:

一行，在所有人都一起上火车的前提下最早在第几天可以离开学校,如果不能离开请输出“G!”
示例1

输入

复制 
7 5
100 100
99 100
95 100
900 1000
0 1000

输出

复制 
4