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
6
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~.
Comments
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.
Evil time out! I'm not sure where to look for more speed, any pointers would be most appreciated....
Thanks
This comment is hidden due to too much negative feedback. Show it anyway.
Tfw you misread the problem and spend hours debugging.