panda-and-shopping-1

Panda loves to shop! And well, anyone who loves to shop gets a huge amount of happiness even after a tiring session of window shopping.

There are N shops, all aligned linearly having index 1,2,3 ... N. Buying any positive number of items from a shop S_i gives a happiness equal to H_i . Unfortunately due to some unavoidable circumstances, every shop owner has introduced a value L_i. You are credited H_i happiness from the ith shop if and only if this is the first shop you are buying something from or you buy atleast one item from this shop and the last shop you shopped from was S_j such that L_j ≤ L_i and j < i. Find the maximum sum of happiness that can be obtained following the rules given above!

Input Format:

The first line contains N , the number of shops in the area. Each of the next N lines contains two space separated integers, H_i and L_i , which denotes the values for the ith shop (defined in the problem statement).

Output Format:

Output consists of one line, which contains the maximum sum of happiness that can be obtained!

Constraints :

 1 ≤ N ≤ 10^5
1 ≤ abs(H_i) ≤ 10^5
1 ≤ L_i ≤ 10^{18}

SAMPLE INPUT
5
10 2
-10 1
5 2
5 2
10 3

SAMPLE OUTPUT
30

Explanation

Excluding the 2nd item, you can buy from all other shops! Hence, sum = 10 + 5 + 5 + 10 = 30.

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Range queries

Segment trees revisited


Solutions: