Se consideră un șir de N numere naturale. O parte dintre poziţiile șirului sunt nevirusate și acest lucru este marcat prin faptul că valoarea de la acele poziţii este 0. Restul poziţiilor sunt virusate și valoarea nenulă de la o poziţie virusată reprezintă costul cu care ea poate fi devirusată. Devirusăm o parte dintre poziţii și dorim ca în final să avem exact K poziţii nevirusate, iar costul total al devirusării să fie minim. O poziţie poate fi devirusată la un moment dat, dacă și numai dacă are cel puţin o poziţie vecină nevirusată. După devirusarea unei poziţii costul asociat acesteia se adună la costul total, poziţia devine nevirusată si orice altă poziţie vecină virusată va putea fi ulterior devirusată.

== include(page="template/taskheader" task_id="antivirus") ==

h2. Cerință
 
Cunoscând N, K și șirul de numere naturale să se determine costul minim cu care se pot obţine
la final exact K poziţii nevirusate (incluzând şi poziţiile ce au fost iniţial nevirusate).

Poveste şi cerinţă...

h2. Date de intrare

Fișierul de intrare antivirus.in va conține pe prima linie numărul natural T – numărul de teste. Fiecare test este descris pe două linii. Pe prima linie se găsesc două numere naturale N și K cu semnificația din enunţ si pe a doua linie N numere naturale reprezentând elementele șirului.

Fişierul de intrare $antivirus.in$ ...
 
h2. Date de ieşire
 
În fişierul de ieşire $antivirus.out$ ...
 
h2. Restricţii
 
* $... ≤ ... ≤ ...$
 
h2. Exemplu

h2. Date de ieșire

table(example). |_. antivirus.in |_. antivirus.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

Fișierul de ieșire antivirus.out trebuie să conțină T linii. Pe fiecare linie va fi afișat răspunsul pentru un test - un număr natural reprezentând costul minim al unei devirusări astfel încât în final șirul să conțină exact K poziții nevirusate – inclusiv cele care erau inițial nevirusate.

h3. Explicaţie

h2. Restricții și precizări

...

• 1 ≤ T ≤ 4
• 1 ≤ K ≤ N ≤ N
• pentru teste în valoare de 10 puncte se garantează că N ≤80
• pentru alte teste în valoare de 20 puncte se garantează că N ≤200
• pentru alte teste în valoare de 10 puncte în şirul iniţial există exact o poziție nevirusată
• pentru alte teste în valoare de 10 puncte în şirul iniţial există exact 2 poziții nevirusate

== include(page="template/taskfooter" task_id="antivirus") ==