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

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

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$ ~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^\text{th}$ ~i^\text{th}~ $(1 \le i \le N)$ ~(1 \le i \le N)~ neighbour is located at $x_i$ ~x_i~ metres from the origin, and this neighbour's pie has enough sugar for your Fax to run a distance of $d_i$ ~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$ ~0~ metres from the origin $(x_1 = 0)$ ~(x_1 = 0)~. At time $0$ ~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 will contain $N$ ~N~ $(1 \le N \le 2000)$ ~(1 \le N \le 2000)~.

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

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

For 2 of the 15 available marks, $x_i \ge 0$ ~x_i \ge 0~.
For an additional 3 of the 15 available marks, $-100 \le x_i \le 100$ ~-100 \le x_i \le 100~.
For an additional 3 of the 15 available marks, $N \le 6$ ~N \le 6~.
For an additional 3 of the 15 available marks, $N \le 20$ ~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

Sample Input 2

2
0 10
11 10

Sample Output 2

Sample Input 3

Sample Output 3

Comments

5

TheKrishnan commented on Feb. 20, 2017, 8:28 p.m.

Does the sugar carry on from neighbour to neighbour? So if not all sugar is used from one neighbour to next, does it carry on?

5

d commented on Feb. 20, 2017, 8:32 p.m.

Yes, all of the previous sugar can still be used up.