Как оптимизировать алгоритм для нахождения максимальной грузоподъемности?

Есть задача из codeforce.

Суть в том, что у нас есть грузовик с возможностью перевозить v предметов. Всего два типа предметов: байдарки (тип 1) и катамараны (тип 2). Каждый объект обладает своим весом p. Необходимо найти максимальную грузоподъемность набора.

Например:

3 2
1 11
2 20
1 10

Ответ тут будет:

21
1 3

Я решил реализовать такую идею. У меня есть объект - Target(type, weight, index). Массив из таких объектов я сортирую, потом прохожусь по отсортированному массиву и пытаюсь сделать три суммы:

1. Только для байдарок

2. Только для катамарана

3. Смешанные

Понятное дело, что сумма накладывается в ограничение грузоподъемности.

 private static void solve() {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int weight = input.nextInt();

        List<Target> targets = new ArrayList<>();

        String first = "";
        int firstSum = 0;
        int firstLoad = 0;

        String second = "";
        int secondSum = 0;
        int secondLoad = 0;

        String third = "";
        int thirdSum = 0;
        int thirdLoad = 0;

        for (int i = 0; i < n; i++) {
            Target target = new Target(input.nextInt(), input.nextInt(), i + 1);
            targets.add(target);
        }

        Collections.sort(targets);

        for (int i = n - 1; i >= 0; i--) {
            // First case
            if (targets.get(i).type == 1 && firstLoad + 1 <= weight) {
                firstSum += targets.get(i).weight;
                firstLoad += 1;
                first += targets.get(i).index + " ";
            }

            // Second case
            if (targets.get(i).type == 2 && secondLoad + 2 <= weight) {
                secondSum += targets.get(i).weight;
                secondLoad += 2;
                second += targets.get(i).index + " ";
            }

            // Mixed case
            if (thirdLoad + targets.get(i).type <= weight) {
                thirdSum += targets.get(i).weight;
                thirdLoad += targets.get(i).type;
                third += targets.get(i).index + " ";
            }
        }

        int result = Math.max(firstSum, Math.max(secondSum, thirdSum));
        System.out.println(result);

        if (result == firstSum) {
            System.out.println(first);
        } else if (result == secondSum) {
            System.out.println(second);
        } else {
            System.out.println(third);
        }
    }

Но данное решение обламывается на таком тестовом наборе:

20 19
2 47
1 37
1 48
2 42
2 48
1 38
2 47
1 48
2 47
1 41
2 46
1 28
1 49
1 45
2 34
1 43
2 29
1 46
2 45
2 18

Я получаю

600
13 8 5 3 9 7 1 18 11 19 14 16 10 

А должен:

630
13 8 3 18 14 16 10 6 2 5 9 7 1 11

Разница тут в таком наборе:

Вывод
600
    19  

Ответ
630
    6 2  

Как это вылечить?