계란으로 계란치기

원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 못 하는 것이라고 하지만, 인범이는 3대 500의 합계가 500을 넘는 몇 안 되는 프로그래머 중 한 명이다. 인범이는 온라인 저지에서 틀린 제출을 할 때마다 턱걸이를 5회 하며 뇌와 근육을 함께 단련한다. 근육을 키우려면 식단이 중요하다는 것을 아는 인범이는 아침으로 밥이나 빵 대신 단백질이 많은 계란찜을 만들어 먹는다.

계란찜을 만들려면 계란을 깨야 한다. 그런데 힘이 너무 센 인범이가 부엌 대리석에 계란을 치면 껍데기가 산산조각 나서 뒤처리가 어렵다. 고민하던 인범이에게 유현이가 좋은 방법을 알려주었다. 계란으로 계란을 치는 것이다. 계란끼리 부딪히면 껍데기가 깔끔하게 갈라진다는 것을 확인한 인범이는 앞으로 계란으로 계란을 쳐서 식사를 준비하기로 했다. 유현이는 요리를 하면서도 두뇌를 단련할 수 있는 퍼즐도 함께 알려주었다.

각 계란에는 내구도와 무게가 정해져 있다. 두 계란이 부딪치면 각 계란의 내구도가 상대 계란의 무게만큼 줄어든다. 내구도가 0 이하가 되면 계란이 깨진다. 예를 들어 계란 1의 내구도가 7, 무게가 5이고 계란 2의 내구도가 3, 무게가 4라고 하자. 계란 1로 계란 2를 치면 계란 1의 내구도는 4 줄어 3이 되고, 계란 2의 내구도는 5 줄어 -2가 된다. 이 충돌로 계란 1은 깨지지 않고 계란 2는 깨진다.

유현이가 알려준 퍼즐은 일렬로 놓인 계란을 대상으로 한다. 왼쪽부터 차례로 계란을 하나씩 들고, 각 계란이 다른 계란을 한 번씩만 쳐서 최대한 많은 계란을 깨는 문제다. 과정은 다음과 같다. (1) 가장 왼쪽의 계란을 든다. (2) 손에 든 계란으로 깨지지 않은 다른 계란 중 하나를 친다. 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 그 후 손에 든 계란을 원래 자리에 내려놓고 (3)으로 간다. (3) 가장 최근에 든 계란의 오른쪽 한 칸 계란을 들고 (2)를 다시 진행한다. 가장 최근에 든 계란이 가장 오른쪽에 있으면 과정을 끝낸다.

이 과정으로 깰 수 있는 계란의 최대 개수를 구하라. 각 계란의 내구도와 무게가 순서대로 주어진다.

첫째 줄에 계란의 수 $N$ ($1 \le N \le 8$)이 주어진다. 다음 $N$개의 줄에는 계란의 정보가 주어진다. $i+1$번째 줄에는 왼쪽에서 $i$번째 계란의 내구도 $S_i$ ($1 \le S_i \le 300$)와 무게 $W_i$ ($1 \le W_i \le 300$)가 빈칸을 사이에 두고 주어진다.

첫째 줄에 인범이가 깰 수 있는 계란의 최대 개수를 출력한다.