{"raw_statement":[{"iden":"statement","content":"In a building where Polycarp lives there are _equal_ number of flats on each floor. Unfortunately, Polycarp don't remember how many flats are on each floor, but he remembers that the flats are numbered from 1 from lower to upper floors. That is, the first several flats are on the first floor, the next several flats are on the second and so on. Polycarp don't remember the total number of flats in the building, so you can consider the building to be infinitely high (i.e. there are infinitely many floors). Note that the floors are numbered from 1.\n\nPolycarp remembers on which floors several flats are located. It is guaranteed that this information is not self-contradictory. It means that there exists a building with equal number of flats on each floor so that the flats from Polycarp's memory have the floors Polycarp remembers.\n\nGiven this information, is it possible to restore the exact floor for flat _n_?"},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 100, 0 ≤ _m_ ≤ 100), where _n_ is the number of the flat you need to restore floor for, and _m_ is the number of flats in Polycarp's memory.\n\n_m_ lines follow, describing the Polycarp's memory: each of these lines contains a pair of integers _k__i_, _f__i_ (1 ≤ _k__i_ ≤ 100, 1 ≤ _f__i_ ≤ 100), which means that the flat _k__i_ is on the _f__i_\\-th floor. All values _k__i_ are distinct.\n\nIt is guaranteed that the given information is not self-contradictory."},{"iden":"output","content":"Print the number of the floor in which the _n_\\-th flat is located, if it is possible to determine it in a unique way. Print _\\-1_ if it is not possible to uniquely restore this floor."},{"iden":"examples","content":"Input\n\n10 3\n6 2\n2 1\n7 3\n\nOutput\n\n4\n\nInput\n\n8 4\n3 1\n6 2\n5 2\n2 1\n\nOutput\n\n\\-1"},{"iden":"note","content":"In the first example the 6-th flat is on the 2-nd floor, while the 7-th flat is on the 3-rd, so, the 6-th flat is the last on its floor and there are 3 flats on each floor. Thus, the 10-th flat is on the 4-th floor.\n\nIn the second example there can be 3 or 4 flats on each floor, so we can't restore the floor for the 8-th flat."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}