Optimize Memory Usage

Moderate
0/80
Contributed by

Problem statement

Alex has a computer with ‘K’ memory spaces. He has a list of ‘N’ different document downloads that he would like to do, each of which consumes some unique memory usage. He also has ‘M’ computer games, each of which consumes some unique memory usage. His computer can allow at most one download and at most one game to run simultaneously, provided that the sum of memory usages doesn’t exceed ‘K’. Alex wants to play at most one game and complete at most one download so that the total memory usage is maximum.

Given a list ‘download’ and a list ‘game’, help Alex find out the number of pairs of downloads and games such that the sum of memory usages is maximum. It can also be possible that Alex only plays a game or performs a download at a time.

Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10
1 <= N, M <= 10^5
1 <= K <= 10^9

Time Limit: 1 sec
``````
Sample Input 1:
``````2
6 7 6
1 7 2 4 5 6
2 3 4 1 5 8 10
4 3 8
2 1 5 9
9 2 4
``````
Sample Output 1:
``````0 4
2 2
3 0
4 3
5 -1
2 1
``````
Explanation for Sample Input 1:
``````In test case one, if we check the pairs, we can see that the maximum permitted memory that we can use is 6. The pairs (0, 4), (2, 2), (3, 0), and (4, 3) sum up to 6 memory usages. Also, download number 5 will alone consume 6 memory. So, pair (6, -1) is also valid.
In test case two, the maximum permitted memory usage is 7. Only pair (2, 1) sum up to 7 memory usages.
``````
Sample Input 2:
``````3
2 3 4
1 3
3 1 10
5 6 2
1 3 5 7 9
1 3 5 7 9 11
1 3 5
3
1 2 3
``````
Sample Output 2:
``````0 0
1 1
0 0
0 1
``````
Console