Тут вам повезло. Вы какую-то жадность сделали, но она в общем случае несработает.
Надо делать динамическое программирование:
F(n, k) - максимальная сумма, которую можно получить, взяв какие-то числа из первых n пар и при этом получить k нечетных чисел.
F(0,0) = 0
F(0,*) = -infinity
F(n,k) = max_i=0..1 a[n-1][i]+F(n-1,k-a[n-1][i]%2).
Ответ: max_i=0..n: F(n,i) (т.ч. F(n,i) - той же четно для i<=n//2 и нечетно для i > n//2)