You are given an array arr of length N, representing money with N customers. The i-th customer has arr_i rupees. There is another array cost of length M, representing the cost of M items in a store. The j-th item costs cost_j rupees. The store offers some discount money d which any customer can use to buy an item. Each customer can buy only one item and cannot use his money to buy an item for any other customer.

Task

Determine the maximum number of customers who can buy an item and the minimum total sum of customers’ money spent to achieve maximum customers with an item.

Notes

• Assume 1-Based Indexing.
• The discount money d is common for all the customers, i.e., if one customer spends r rupees from d, then the discount money is reduced to (d-r) for all the customers.
• Multiple customers can spend money from the discount.

Example

Assumptions

• N = 3
• M = 2
• d = 100
• arr = [30, 40, 50]
• cost = [80, 110]

Approach

Initially, we have discount money equals 100.

• 2nd customer buys 1st item worth 80 rupees using 40 rupees of discount money.
• Now the discount money left is 100 - 40 = 60.
• 3rd customer buys 2nd item worth 110 rupees using 60 rupees of discount money.
• The total number of customers who can buy an item is 2 with their total sum of money spent equals 90.

Therefore the answer is [2 90].

Function Description

Complete the function maxCustomers provided in the editor. The function takes the following parameters and returns an array consisting of 2 integers, the maximum number of customers with items, and the minimum total customers' money spent:

• N: Represents the size of array arr
• M: Represents the size of array cost
• d: Represents the value of discount money
• arr: Represents the elements of array arr
• cost: Represents the elements of array cost

Input format

Note: This is the input format you must use to provide custom input (available above the Compile and Test button).

• The first line of the input contains three integers N, M, and d, denoting the number of customers, the number of items, and the discount money.
• The second line of the input contains N integers arr₁, arr₂, …, arr_N, where arr_i is the money with the i-th customer.
• The third line of the input contains M integers cost₁, cost₂, …, cost_M, where cost_j is the price of the j-th item.

Output format

Print two space-separated numbers, the maximum number of customers who can buy an item and the minimum total customers' money needed for buying the maximum number of items.

Constraints

\(1 \leq N \leq 10^5\)
\(1 \leq M \leq 10^5 \)
\(0 \leq d \leq 10^9\)
\(1 \leq arr_{i} \leq 10^4\ \forall \ i \in [\,1,N\,]\)
\(1 \leq cost_{j} \leq 10^9 \ \forall \ j \in [\,1, M\,]\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.