모험가의 여정

N개의 퀘스트가 있다. 각 퀘스트에는 필요한 최소 힘(S)과 최소 지혜(I)가 정해져 있다.

모험가는 처음에 힘=1, 지혜=1을 가진다. 퀘스트를 완료하려면 현재 힘 >= S 이거나 현재 지혜 >= I 이어야 한다.

퀘스트를 완료할 때마다 힘을 1 올리거나 지혜를 1 올리는 것 중 하나를 선택할 수 있다.

완료할 수 있는 퀘스트의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 퀘스트 수 N이 주어진다. (1 <= N <= 15)
둘째 줄부터 N개의 줄에 각 퀘스트의 필요 힘 S와 필요 지혜 I가 공백으로 구분되어 주어진다. (1 <= S, I <= 100)

출력

완료할 수 있는 퀘스트의 최대 개수를 출력한다.

입출력 예시

입력 1

3
1 5
5 1
2 3

출력 1

3

입력 2

3
1 10
2 10
3 5

출력 2

3