[I] I'm GM!

다들 알고 있다시피, hibye1217은 포드코스에서 Grandmaster의 등급을 가지고 있다. 이를 기념할 겸 과거를 돌아보던 hibye1217은 문득 아래와 같은 궁금증을 가지게 되었다.

'만약 일부 대회를 계산에서 제외할 수 있다면 얼마나 더 높은 레이팅을 받을 수 있을까?'

포드코스의 레이팅의 계산 방식은 다음과 같다.

• 유저의 레이팅은 $0$에서 시작한다.
• 포드코스의 각 대회에는 레이팅 상수라는 두 정수 $a$, $b$가 존재한다. 이는 각 대회가 유저의 레이팅에 얼마나 큰 영향을 끼치는지를 의미한다. 레이팅 상수는 대회마다 다를 수 있다.
• 유저가 대회를 치기 전의 레이팅이 정수 $r$이었고, 대회에서의 퍼포먼스가 정수 $p$였다고 하자. 그러면 유저의 새로운 레이팅은 $\displaystyle \frac{ap+br}{a+b}$이 된다.
• 만약 새로운 레이팅이 정수가 아니라면, 소수점 아랫부분이 $0.5$ 미만이라면 내림하고 $0.5$ 이상이라면 올림한다.

포드코스의 Grandmaster인 hibye1217은 $N$개의 대회 중 $0$개 이상의 대회를 계산에서 제외하는 경우의 수는 $2^N$가지 경우나 있으니 쉽게 풀 수 없다는 결론을 냈다. 이제 포드코스의 Legendary Grandmaster인 여****러분들이 이 문제를 효율적으로 풀어 보자!

일부 대회를 계산에서 제외할 수는 있어도 대회 간의 순서를 바꿀 수는 없음에 유의하라.

첫째 줄에는 hibye1217이 참여한 대회의 개수 $N$이 주어진다. $(1 \le N \le 500\,000)$

둘째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에는 hibye1217이 참여한 $i$번째 대회의 레이팅 상수인 두 정수 $a$, $b$와 대회에서의 퍼포먼스인 정수 $p$가 공백으로 구분되어 주어진다. $(1 \le a, b \le 1\,000; 0 \le p \le 4\,000)$

첫째 줄에 일부 대회를 계산에서 제외할 수 있을 때 hibye1217이 받을 수 있는 레이팅의 최댓값을 출력한다.