An olive oil seller needs to measure oi; for customers using only one type of flask. There are many flasks available, each with marking at various levels. Each customer must receive a flask filled to a mark that is atleast equal to the amount ordered. Given a list of customer requirements and a list of flasks with their measurements, determine the single type of flask that will result in the minimal loss to the merchant. Loss is the sum of marking – requirement for each order. Return the zero-based index of the flask type chosen. If there are multiple answers, return the minimum index. If no flask will satisfy the constraints, return -1.
For example, there are n=4 orders for requirements = [4, 6, 6, 7] units of oil. There are m=3 types of flask available with markings = [“3 5 7”, “6 8 9”, “3 5 6”]. These markings are given as 2D array with total_marks rows and 2 columns, first is the index of flask and second the mark. To fill the orders using the flask at markings = [3,5,7], the loss is calculated as marking requirement for each order so, 5-4=1, 7-6=1 and 7-7=0. The total loss then is 1+1+1+0=3. Choosing the flask at markings, the loss is 6-4=2, 6-6=0, 8-7=1 -> 2+0+0+1 = 3. The third flask has a maximum mark at 6 which is smaller than the largest order, so it cannot be used. In this case, flask type 0 is chosen.
Note ! The markings 2d array will be given in order of the flasks, i.e the markings for the 0-index flask will be followed by markings of 1-index flask and so on. For each flask, the given markings will also be in the sorted order.
1 <= n <= 100
-1 <= mat[i][j] <= 1
Sample Input 0
Sample Output 0 :