I can not correctly solve the problem from the exam on infe. Why is the answer wrong?

Question

Algorithms

I wrote the code for the following task from the exam in computer science:

The data set consists of an odd number of pairs of natural numbers. It is necessary to choose exactly one number from each pair so that the parity of the sum of the chosen numbers coincides with the parity of the majority of the chosen numbers, and the sum of the chosen numbers is as large as possible. Determine the maximum amount that can be obtained with this choice. It is guaranteed that a choice satisfying the conditions is possible.

Input example:

5
15 8
5 11
6 3
7 2
9 14

For the specified data, you need to choose the numbers 15, 11, 6, 7 and 14. Most of them are odd, the sum of the selected numbers is 53 and is also odd. The answer is to write the number 53.

You are given two input files (A and B), each with the structure described above. In your answer, indicate two numbers: first, the value of the required amount for file A, then for file B.

The answers to this problem are:

A - 121184
B - 36898658.

Wrote the following code in python:

with open('27-B.txt') as f:
    count_row = int(f.readline())
    count_even, count_odd, total_sum = 0, 0, 0
    diff_array = []
    for row in range(count_row):
        a, b = map(int, f.readline().split())
        max_number = max(a, b)
        if max_number % 2 == 0:
            count_even += 1
        else:
            count_odd += 1
        total_sum += max_number
        diff_array.append(abs(a - b))

diff_array = sorted(diff_array)
i = 0
while True:
    if count_even > count_odd and total_sum % 2 != 0:
        count_even -= 1
        count_odd += 1
        total_sum -= diff_array[i]
    elif count_odd > count_even and total_sum % 2 == 0:
        count_even += 1
        count_odd -= 1
        total_sum -= diff_array[i]
    else:
        print(total_sum)
        break
    i += 1

The algorithm for the task that I came up with works as follows: we
read the maximum number from the line in the file and check its parity, after which we write it to the corresponding counter. We also create an array of all the differences between the numbers, which we later sort in ascending order. We proceed to check the condition of the problem. If the number of even numbers is greater than the odd ones, and the sum is odd, then subtract the first difference and decrease the number of even ones by one, and increase the number of odd ones by one. All this works in a loop and until our condition is met, we will not exit.

As a result, I get the correct answer for A, and for file B - 36898558 .

Please help me find the error and explain it.

I am attaching files for this task:
A:https://inf-ege.sdamgia.ru/get_file?id=79118
B: https://inf-ege.sdamgia.ru/get_file?id=79119

Answer 1

You're in luck here. You have done some kind of greed, but it will not work in the general case.
We need to do dynamic programming:
F(n, k) is the maximum amount that can be obtained by taking some numbers from the first n pairs and at the same time getting k odd numbers.
F(0,0) = 0
F(0,*) = -infinity
F(n,k) = max_i=0..1 a[n-1][i]+F(n-1,ka[n- 1][i]%2).
Answer: max_i=0..n: F(n,i) (including F(n,i) - same even for i<=n//2 and odd for i > n//2)

Answer 2

subtract the first difference and decrease the number of even ones by one, and increase the number of odd ones by one

Are you acting on the assumption that one number in a pair is even and the other is not? This is not true. There can be two even and two odd numbers in a pair.