Company: Amazon_15june
Difficulty: medium
Maximum Sum Compression Utility Developers at Amazon are working on a prototype for a utility that compresses a n x n matrix, data , with the help of a compression rate represented by an array, factor . The utility returns an integer which is the maximum sum of exactly x elements of the matrix such that the number of elements taken from the i th row does not exceed factor[i] . The utility returns -1 if the compression cannot be performed. Given array data and factor , find the maximum sum to perform compression under the given constraints, or -1 if it is not possible. Input Format The first line contains an integer n , the size of the matrix. The second line contains n space-separated integers representing the compression rates for each element of data . The third line contains n space-separated integers representing the square matrix of data . The fourth line contains an integer x , the number of elements to choose. Output Format Return a long integer: the maximum sum if the compressi