Avocado Trees!

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Problem type

Julia likes avocado trees. She maintains a strip of N trees by a river. All of the trees are grown along a straight line. However, Rose the avocado-robber has just made it into town. Rose would like to steal all the avocados from Julia's trees, but she also knows that Julia keeps her trees well guarded. This means that Rose will only get one chance to raid Julia. Additionally, Rose is short, and so can only steal from trees with height at most H. Rose has also decided to not attempt to hit all the trees, but will instead focus on one contiguous range of trees (presumably to lower chances of being seen).

Rose has created a list of all the ranges she is considering to steal from. Since she can only steal from one range before having to escape, write a program to find the maximum number of avocados she can steal.

Input Specification

The first line will contain three integers: N (2 \le N \le 10^6), denoting the number of trees Julia has, Q (1 \le Q \le 10^6), the number of possible ranges Rose has on her list, and H (1 \le H \le 10^6), the maximum height Rose can steal from.

The next N lines will contain two integers: a_i (1 \le i \le N, 1 \le a_i \le 10^6), denoting the height of the tree at position i, and b_i (1 \le b_i \le 10^3), denoting the avocado yield of that particular tree.

The next Q lines will contain two integers l and r (1 \le l \le r \le N), denoting that the range Rose has chosen begins at l and ends at r (inclusive).

Output Specification

Output a single integer, the maximum number of avocados Rose can obtain from a single range.

Sample Input

5 2 3
1 3
4 2
3 3
2 1
1 1
1 3
2 5

Sample Output


Explanation for Sample Output

The first range is from tree 1 to tree 3, which will give Rose 6 avocados since the tree at index 2 is too tall for Rose to steal from. The second range from tree 2 to tree 5 will only yield 5 avocados. Therefore, the maximum number of avocados that can be obtained from a single range is 6.


  • 0
    JollyJuniperus  commented on May 25, 2024, 10:29 a.m. edit 3

    I have no qualms whatsoever about posting this Python hint: if you're stuck, compare run times in Python 3 vs. PyPy3! Or, check out the About > Tips section of DMOJ to optimise I/O.

  • 1
    Lawlessjoe  commented on April 21, 2022, 8:25 p.m.

    Evil time out! I'm not sure where to look for more speed, any pointers would be most appreciated....


  • 14
    SuperClash  commented on Feb. 5, 2021, 12:07 a.m. edited

    Tfw you misread the problem and spend hours debugging.