Find an element from list a and b such that the sum of their values is less or equal to target and as close to target as possible

https://leetcode.com/discuss/interview-question/373202/amazon-oa-2019-optimal-utilization Given 2 lists a and b. Each element is a pair of integers where the first integer represents the unique id and the second integer represents a value. Your task is to find an element from a and an element form b such that the sum of their values is less or equal to target and as close to target as possible. Return a list of ids of selected elements. If no pair is possible, return an empty list.

question was this but I had to use Lists (like <<1,1>, <2,2> <3,3>>)

my solution was something like below. I kept failing some test cases with a NullPointerException. I am trying to find out WHAT SPECIFIC INPUT(foreground, background) COULD HAVE CAUSED THIS. (the assessment website HID the error line). the problem did not have any specifications or guarantees like 0 < deviceCapacity < 1000000, so I do NOT know what was passed in

Things I checked for: foreground and background were not null. they did not have null values (how i checked is below)

I put a System.out.println(foregroundApplications.get(i)); System.out.println(backgroundApplications.get(j)) just before initializing "sums", the goal being to see if any values were something like null or <null, null>, but they were all valid number pairs like <1,8>. (if it was null, it would have printed null right? unsure about this). example of what I saw (there were no nulls): <1, 14> <2, 14> <3, 14> <4, 14>

i checked in the beginning if the lists (foreground and background) were null with an if(foregroundApps == null), they weren't.

I can't change my code anymore, this was an assessment with obfuscated test cases which I am trying to figure out.

P.S. If there is a better approach than O(M*N) time, I would like to know

public List<List<Integer>> optimize(int deviceCapacity, List<List<Integer> foregroundApplications, List<List<Integer>> backgroundApplications)
{

TreeMap<Integer, List<List<Integer>>> map = new TreeMap<>();

for(int i = 0; i < foregroundApplications.size(); i++)
{
    for(int j = 0; j < backgroundApplications.size(); j++)
    {
        int sum = foregroundApplications.get(i).get(1) + backgroundApplications.get(j).get(1);
        if(sum<=deviceCapacity)
        {
            List<List<Integer>> list= new ArrayList<>();
            if(map.containsKey(sum))
            {
                list = map.get(sum);
            }
            List<Integer> pair = new ArrayList<>();
            pair.add(foregroundApplications.get(i).get(0));
            pair.add(backgroundApplications.get(j).get(0));
            list.add(pair);
            map.put(sum, list);
        }
    }
}

if(map.size() == 0)
{
    List<List<Integer>> list= new ArrayList<>();
    List<Integer> emptyPair = new ArrayList<>();
    emptyPair.add(null);
    emptyPair.add(null);
    list.add(emptyPair);
    return list;
}


return map.get(map.lastKey());

}