소 전시회

"Fat and docile, big and dumb, they look so stupid, they aren't much fun..."

• Cows with Guns by Dana Lyons

소들은 자신들이 똑똑하고 재미있다는 것을 대중에게 증명하려고 한다. 이를 위해 Bessie가 소들이 참여하는 전시회를 준비했다. Bessie는 $N$마리($1 \le N \le 100$)의 소 각각을 면담하고, 소 $i$마다 두 값을 정했다. 똑똑함 $S_i$($-1000 \le S_i \le 1000$)와 재미 $F_i$($-1000 \le F_i \le 1000$)이다.

Bessie는 전시회에 데려갈 소를 고른다. 그룹의 총 똑똑함 $TS$는 $S_i$의 합이고, 총 재미 $TF$는 $F_i$의 합이다. Bessie는 $TS + TF$를 최대화하려고 하지만, $TS$와 $TF$는 모두 0 이상이어야 한다. 두 값이 음수가 되지 않도록 $TS + TF$를 최대로 만들어야 한다.

첫 줄에 소의 수를 나타내는 정수 $N$이 주어진다. 이어지는 $N$개의 줄에는 소 $i$의 똑똑함 $S_i$와 재미 $F_i$가 공백으로 구분되어 주어진다.

$TS$와 $TF$가 모두 0 이상인 경우의 $TS + TF$ 최댓값을 한 줄에 출력한다. 그러한 소의 조합이 없으면 $0$을 출력한다.

Bessie는 1번, 3번, 4번 소를 고른다. $TS = -5 + 6 + 2 = 3$이고 $TF = 7 - 3 + 1 = 5$이므로 $TS + TF$는 8이다. 2번 소를 추가하면 $TS + TF$가 10이 되지만, $TF$가 음수가 되므로 허용되지 않는다.