TLE '16 Contest 6 (Mock CCC) S3 - Hyper Fax


Submit solution


Points:15 (partial)
Time limit:2.0s
Memory limit:256M

Problem type

Fax McClad walking his pet Fax in his neighbourhood.

You live in a neighbourhood which is arranged as a straight line.

Your pet Fax is very popular among the N neighbours, so they will feed pies to your pet.

Initially, your Fax is lazy and unable to move, but when he consumes sugar, he becomes hyper and begins to run.

The i^{th} (1 \le i \le N) neighbour is located at x_i metres from the origin, and this neighbour's pie contains enough sugar for your Fax to run a distance of d_i more metres while hyper. The neighbours are extremely kind and enjoy feeding their entire pie to your Fax. The neighbours only have 1 pie each, so your Fax can only eat a neighbour's pie on one visit.

You are the first neighbour, and you are located at 0 metres from the origin (x_1 = 0). At time 0, your pet Fax is located at the origin, and you feed your pie to your Fax.

What is the maximum distance that your Fax can travel while hyper?

Input Specification

The first line contains N (1 \le N \le 2000).

For each of the next N lines, the i^{th} line will contain x_i (-10^9 \le x_i \le 10^9) and d_i (1 \le d_i \le 10^9). Also, x_1 = 0.

No two neighbours share the same x_i. The sum of all d_i will not exceed 10^9.

  • For 2 of the 15 available marks, x_i \ge 0.
  • For an additional 3 of the 15 available marks, -100 \le x_i \le 100.
  • For an additional 3 of the 15 available marks, N \le 6.
  • For an additional 3 of the 15 available marks, N \le 20.

Output Specification

Output one integer, which is the maximum total distance that your Fax can travel while hyper.

Sample Input 1

2
0 10
-10 10

Sample Output 1

20

Sample Input 2

2
0 10
11 10

Sample Output 2

10

Sample Input 3

3
0 2
1 2
-1 2

Sample Output 3

6

Comments

There are no comments at the moment.