Začneme tým, že si vyriešime jednoduchšiu úlohu: odignorujeme zatiaľ, že máme nejakých internov, a budeme sa zaujímať len o to, koľko najmenej čísel treba zmeniť, aby medián vyšiel presne $m$.

Predstavme si, že sme si všetky hodnoty usporiadali a pozreli sme sa do stredu poľa. Ak v strede poľa vidíme želanú hodnotu $m$, netreba meniť nič.

Ak vidíme hodnotu menšiu ako $m$, máme v poli priveľa malých čísel. Zistime si teda, pokiaľ v našom poli siahajú čísla menšie ako $m$. Nech sú primalé čísla nielen v strede poľa, ale aj na nasledujúcich $x-1$ políčkach. Čo to pre nás znamená? Aspoň $x$ spomedzi čísel v pôvodnom poli nutne musíme zväčšiť na aspoň $m$, inak budeme mať ešte stále priveľa malých čísel a v strede usporiadaného poľa bude naďalej primalá hodnota.

Na druhej strane však ľahko nahliadneme, že keď zmeníme ľubovoľných $x$ primalých hodnôt na hodnotu presne $m$, dostaneme platné riešenie. Totiž keď po tejto zmene preusporiadame prvky, prvky s novou hodnotou $m$ obsadia presne $x$ posledných políčok z úseku, v ktorom dovtedy boli primalé hodnoty – a teda aj v strede poľa už dostaneme hodnotu $m$.

Situácia, keď sme v strede poľa uvideli priveľkú hodnotu, sa rieši symetricky.

Späť k pôvodnej úlohe

Bez ujmy na všeobecnosti predpokladajme, že súčasný medián je primalý, potrebujeme teda niektoré prvky zväčšiť. A vyššie popísaným spôsobom vieme nájsť $x$ také, že určite treba spraviť aspoň $x$ zmien.

Pre každého interna si teraz zistíme, koľko má medzi svojími meraniami čísel menších ako $m$. Nanajvýš toľko ich samozrejme tento konkrétny intern vie zväčšiť na $m$. My hľadáme takú sadu internov, aby ich bolo čo najmenej a aby dokopy vedeli zväčšiť aspoň tých potrebných $x$ hodnôt. Je zjavné, že toto vieme spraviť pažravo: usporiadame si internov podľa toho, koľko hodnôt vedia zväčšiť na $m$, a budeme ich postupne brať (začínajúc tým, ktorý vie zmien spraviť najviac) až kým nebudú dokopy vedieť spraviť dostatočný počet zmien.

Zjavne platí, že keď nami vybraná skupina internov spraví ľubovoľných $x$ zmien (hodnoty menšej ako $m$ na hodnotu $m$), dostaneme platné riešenie. A tiež platí, že žiadna menšia skupina internov takto veľký počet zmien nevie spraviť, nájdené riešenie je teda optimálne.

Implementácia

K implementácii už len podotknem, že usporadúvať samotné čísla vôbec netreba – totiž si stačí v lineárnom čase spočítať, koľko je primalých a koľko je priveľkých. Pri usporadúvaní internov podľa počtu dobrých zmien, ktoré vedia spraviť, som použil CountSort, celkovo má teda nižšie uvedená implementácia časovú zložitosť lineárnu od veľkosti vstupu: $O(ab)$.

A, B, M = [ int(_) for _ in input().split() ]
data = [ [ int(_) for _ in input().split() ] for a in range(A) ]

pocet_mensich = sum( x<M for row in data for x in row )
pocet_vacsich = sum( x>M for row in data for x in row )
max_moze      = (A*B - 1) // 2
zmenit        = 0
zmenitelny    = lambda x: False

if pocet_mensich > max_moze:
    zmenit = pocet_mensich - max_moze
    zmenitelny = lambda x: x < M

if pocet_vacsich > max_moze:
    zmenit = pocet_vacsich - max_moze
    zmenitelny = lambda x: x > M

# pocet_internov[x] bude pocet internov, ktori vedia spravit presne x zmien
pocet_internov = [ 0 for _ in range(B+1) ]
for row in data:
    pocet_internov[ sum( zmenitelny(x) for x in row ) ] += 1

vybrat = 0
for b in range(B,0,-1):
    while zmenit > 0 and pocet_internov[b] > 0:
        pocet_internov[b] -= 1
        zmenit -= b
        vybrat += 1

print(vybrat)