문제

프로그래밍 문제를 열심히 풀던 대신이는 어느새 solved.ac 프로필에 표시되는 8대 태그 중 여섯 개의 태그 레이팅을 800 이상으로 만들었다. '균형의 지배자─골드' 뱃지를 받고 기뻐하던 대신이는 욕심이 생겼다. 이제는 '균형의 창조자─골드' 뱃지를 가지고 싶어진 것이다. 뱃지를 위해서는 구현 문제와 기하 문제를 풀어야 한다...

대신이는 열심히 문제들을 검색하여 자신의 실력으로 풀 수 있는 구현 문제와 기하 문제를 모았다. 각 문제들은 대신이의 구현 태그 레이팅과 기하 태그 레이팅 둘 중 적어도 하나를 올려 준다. 모아놓고 보니 문제가 너무 많아서, 대신이는 가능한 한 적은 수의 문제를 풀어 효율적으로 뱃지를 얻고 싶어졌다.

대신이가 지금보다 구현 태그 레이팅을 이상, 기하 태그 레이팅을 이상 더 올려서 '균형의 창조자─골드' 뱃지를 얻을 수 있도록 대신이가 풀어야 하는 최소한의 문제 수를 알려주는 프로그램을 만들자! 특정 문제의 해결 여부가 다른 문제의 태그 레이팅 증가량에 영향을 미치지 않는다.

입력

첫번째 줄에 대신이가 모은 문제의 수를 나타내는 정수 , 대신이가 '균형의 창조자─골드' 뱃지를 얻기 위해 필요한 구현 태그 레이팅과 기하 태그 레이팅을 나타내는 정수 가 공백으로 구분되어 주어진다.

두번째 줄부터 번에 걸쳐, 그중 번째 줄에 대신이가 번 문제를 풀었을 때 증가하는 구현 태그 레이팅과 기하 태그 레이팅을 나타내는 두 정수 가 공백으로 구분되어 주어진다.

출력

대신이가 주어진 문제 중 일부 혹은 전부를 풀어 '균형의 창조자─골드' 뱃지를 얻을 수 있다면, 뱃지를 얻기 위해 풀어야 하는 문제의 수 중 최솟값을 출력한다.

만일 주어진 모든 문제를 풀어도 '균형의 창조자─골드' 뱃지를 얻을 수 없다면, 대신 -1을 출력한다.