Maximizing Dumpling Flavors

JOI has a delicious set meal consisting of $N$ xiaolongbao (soup dumplings) arranged in a line and numbered from $1$ to $N$. The distance between dumpling $i$ and dumpling $j$ is given by $|i-j|$. Initially, each dumpling has a flavor value of $0$. JOI will eat the dumplings in a chosen order. When he eats dumpling $i$, its hot soup spreads to all uneaten dumplings whose positions $j$ satisfy

[ i - D_i \le j \le i + D_i, ]

and each such dumpling has its flavor increased by $A_i$. That is, if dumpling $i$ is eaten, then for every dumpling $j$ that has not yet been eaten and satisfies

[ |i-j| \le D_i, ]

its flavor increases by $A_i$. When a dumpling is eaten, its current flavor is added to JOI’s total taste score. JOI can decide the eating order to maximize the total taste score.

Given the number of dumplings $N$ and for each dumpling the parameters $A_i$ and $D_i$, find the maximum total taste score that JOI can achieve by choosing an optimal eating order.

Input Format:

• The first line contains one integer $N$.
• The next $N$ lines each contain two integers $A_i$ and $D_i$ for dumpling $i$.

• Output a single integer, the maximum total taste score.

inputFormat

The first line contains an integer $N$ $(1 \le N \le 15)$ representing the number of dumplings. Each of the following $N$ lines contains two space‐separated integers $A_i$ and $D_i$, where $A_i$ is the amount by which the flavor increases for dumplings within range when dumpling $i$ is eaten, and $D_i$ is the spreading range.

outputFormat

Output one integer, the maximum total taste score JOI can obtain by choosing an optimal order to eat the dumplings.

sample

3
5 1
-3 1
2 1

7