Hamid is visiting a fair near his village. There are N shops of toys arranged in a line from left to right numbered 1 to N. There are two types of toys in each shop. The toy of type 1 costs A[i] coins and the toy of type 2 costs A[i] coins. Now, he asks you to solve Q queries for him. Each query will be of type-> l r x y -> He visits each shop from l to r in this order and he will buy exactly one toy from each of the visited shops. But, he wants to buy at least x toys of type 1 and at least y toys of type 2. Help him find the minimum cost for buying the toys. Since the answer can be large, return it modulo 10^9 + 7. Problem Constraints 1 <= N, Q <= 10^5 1 <= l <= r <= N 0 <= x + y <= r-l+1 1 <= A[i], A[i] <= 10^9 Input Format The first argument contains a 2D array A of size N x 2, denoting the prices of toys. The second argument contains a 2D array B of size Q x 4, denoting the queries. Output Format Return an array of size Q denoting the answers to the queries. Input 1: A : [ [1, 2] [4, 2] [3, 2] [4, 3] ] B : [ [2, 3, 1, 1] [1, 4, 2, 1] ] Input 2: A : [ [2, 3] [4, 5] [2, 1] ] B : [ [2, 3, 0, 1] ] Example Output Output 1: [5, 9] Output 2: 
I am applying segment tree and storing sorted prices of both types of toys in every node. But not sure hot to apply the x and y constraints mentioned in the query to minimize total price. Also only one toy can be purchased from a particular shop. Please suggest correct way for maintaining segment tree . Thanks in advance :)
Edit : Problem is from a contest which is completed now :)
Edit : Waiting for someone to throw some light on how to solve this problem. Please help!!