I am trying to solve an algorithmic problem that is described as follows:

There are K types of items and 2 supermarkets. Each selling all K types of items but at different prices. Please find the maximum number of unique items that can be bought given that we can spend only X dollars in supermarket 1 and Y dollars in supermarket 2.

Bounds:

1 <= K <= 2000
1 <= X, Y <= 10000

Example:

K = 5, X = 6, Y = 12

Supermarket 1 (We have 6 dollars):

Type 1: 5
Type 2: 1
Type 3: 5
Type 4: 6
Type 5: 3

Supermarket 2 (We have 12 dollars):

Type 1: 3
Type 2: 5
Type 3: 4
Type 4: 6
Type 5: 7

In this case, the optimal answer would be 4 because we can buy item types 1 and 2 in supermarket 1, item types 3 and 4 in supermarket 2.

Problem source: here

I have interpreted it as a coin change problem where one must collect the maximum number of different denominations. Hence, I don't think that a greedy algorithm can work here (since it fails for coin change). More precisely, if one sorts the 2 item lists according to item-price pairs, it would clearly fail since one type of item may be very expensive in both lists.

The next method of my list is to use DP. But, I think DP might be too slow.

Could anyone please advise me on a better solution to solve this problem?

Edit:

I managed to solve the problem thanks to data_h and Deemo's help in the comments. The complete solution can be found here

Once again, thanks a lot for all your help!