Description

The cows want to prove that they are smart and funny. To this end, Bessie is organizing a cow exhibition. She has interviewed $N$ cows and determined each cow’s smartness and fun.

Bessie may choose which cows to include. Because negative smartness or fun would have adverse effects, she does not want the total smartness to be negative, nor the total fun to be negative. Subject to both constraints, she wants to maximize the sum of smartness and fun over the selected cows. Help Bessie compute this maximum.

Input Format

The first line contains a single integer $N$ ($1 \le N \le 400$).

Lines $2$ through $N+1$: the $(i+1)$-th line contains two integers $S_i$ and $F_i$, the smartness and fun of the $i$-th cow ($-1000 \le S_i, F_i \le 1000$).

Output Format

Output a single integer: the maximum possible sum of smartness and fun. Bessie may choose no cows; if that is optimal, output $0$.

5
-5 7
8 -6
6 -3
2 1
-8 -5

8

Hint

Select cows $1$, $3$, and $4$: the smartness sum is $-5 + 6 + 2 = 3$, and the fun sum is $7 - 3 + 1 = 5$.

Adding cow $2$ would raise the total to $10$, but the fun sum would become negative, which is not allowed.

Translated by ChatGPT 5