the point XX in the mall at time TT, and you should find the minimum distance Dr.D needs to walk with decorations. However, if it is impossible to buy one decoration of each type or if Dr.D would have to wait for some shops to open in order to do that, he will go back home and destroy Christmas. We know that Dr.D is extremely smart, so he will choose the shops to buy decorations from optimally.
Since it's almost Christmas, Dr.D wants to get in "That Christmas Feeling". As the first step, he's going to decorate his home. Since he's out of Christmas decorations, he must go buy some at the mall. There are exactly KK types of Christmas decorations and Dr.D wants to buy exactly one decoration of each type.
The mall can be viewed as a sequence of NN shops (numbered 11 through NN) in a straight line. For each valid ii, the ii-th shop is located at the point PiPi, it sells only decorations of the type DiDi and it is only open in the time interval [Li,Ri][Li,Ri]. Dr.D wants to choose a point inside the mall, park his car there and start shopping for KK decorations. Since decorations are rather heavy, whenever Dr.D buys a decoration, he must load it into the car before buying another one. Shopping and moving around the mall (with or without decorations) does not take any time, but bringing heavy decorations back to the car still takes a lot of effort, so Dr.D would like to minimise the total distance he needs to walk with decorations.
You should answer QQ queries. In each query, you are given two integers XX and TT - Dr.D parks at the point XX in the mall at time TT, and you should find the minimum distance Dr.D needs to walk with decorations. However, if it is impossible to buy one decoration of each type or if Dr.D would have to wait for some shops to open in order to do that, he will go back home and destroy Christmas. We know that Dr.D is extremely smart, so he will choose the shops to buy decorations from optimally.
Input:
3 5 2
4 1 3 8
7 2 1 13
9 1 5 7
8 5
8 8
5 7
3 2
2 6
Output:
2
5
3
-1
7
Step by step
Solved in 2 steps with 1 images
