Hi recently had phone screen with Amazon after 35 mins of LP was asked below question

Given 'budget' and prices for each category of ads (mxn int array), pick one price from each category and maximize the budget utilization

budget = 30
adPrices=
[3,1,5,7,10]
[7,9,2,20,10]
[3,1,9,45,51]

ans = 30 (take 7 from first, 20 from second and 3 from third category) thanks @lakh for correction

I came up with a greedy approach by sorting each array and then using heap to move my indices starting with lowest in each category, but this didn't work for some cases - O (mn Max(log m, log n)). Brute force is n^m, any ideas?