8. Algorytmycké problémy

V nie až tak vzdialenej budúcnosti už všetkých prestalo baviť robiť pokusy na potkanoch, preto zvolili nové pokusné zviera: mačiatka. Mačiatka sú oveľa inteligentnejšie ako väčšina potkanov, preto aj výskum na nich môže byť oveľa komplikovanejší. Výskumníci na Matfyze na katedre aplikovaných neľudských pokusov na zvieratách sa momentálne zaoberajú výskumom, ako mačiatka reagujú na riešenie rôznych algoritmických problémov. ¹

Vedci si všimli jednu pozoruhodnú vec. Mačiatka sú síce veľmi inteligentné, ale aj veľmi lenivé. Keď si zapnú contest, vyriešia ho takmer okamžite, ale nechce sa im kódiť. ² Preto skôr ako začnú kódiť, rozmyslia si mačky, aké známe algoritmy budú potrebovať na vyriešenie jednotlivých úloh. Všetky tieto algoritmy najprv naprogramujú, a potom ich už iba v každej úlohe použijú, teda nemusia nič kódiť viac krát.

Po dlhom a náročnom výskume vedci z katedry zistili pre každý známy algoritmus, koľko antipotešenia prinesie mačke, kým ho nakódi.³ Rovnako pre úlohy v conteste je ľahké povedať, koľko potešenia prinesie mačke, ak ju vyrieši a tiež aké algoritmy sú potrebné na jej vyriešenie. Všetok ostatný kód okrem algoritmov je z hladiska potešenia irelevantný.

Keďže však algoritmické mačky sú drahé, chceli by vedci zistiť, koľko najviac potešenia by taká mačka mohla získať, ak by riešila nejaký contest. Keďže však túto úlohu nemôžu dať vyrátať mačkám, lebo – ako som povedal – sú drahé, uchýlili sa vedci k lacnejšej alternatíve: vám. Tak šup šup, makaj a počítaj!

Úloha

Dostanete popis jedného contestu a všetkých algoritmov, ktoré mačky poznajú. Pre každý algoritmus máte zadané, koľko antipotešenia mačke prinesie, ak ho nakódi. Tiež pre každý problém contestu viete, koľko potešenia mačke prinesie, ak ho vyrieši, a ktoré algoritmy sú potrebné na jeho vyriešenie. Na vyriešenie problému potrebuje mačka nakódiť všetky tieto algoritmy. Všetko ostatné je z hľadiska potešenia irelevantné

Každý algoritmus stačí nakódiť raz, a každý problém sa dá vyriešiť najviac raz (keď mačka aj odovzdá viac krát to isté už ju to znovu nepoteší).

Vašou úlohou je zistiť, koľko najviac potešenia vie mačka za daný contest získať, teda maximálnu hodnotu súčtov potešenia za problémy mínus súčtov antipotešenia za algoritmy.

Formát vstupu

V prvom riadku vstupu sú čísla \(n, m\) (\(1 \leq n, m \leq 200\)) postupne udávajúce počet problémov v conteste a počet známych algoritmov.

V druhom riadku je \(n\) medzerou oddelených čísel \(a_1,\dots,a_n\), pričom číslo \(a_i\) (\(0 \leq a_i \leq 10^9\)) určuje počet získeného potešenia za vyriešenie problému \(i\).

V treťom riadku je \(m\) medzerou oddelených čísel \(b_1,\dots,b_m\), pričom číslo \(b_j\) (\(0 \leq b_j \leq 10^9\)) určuje počet antipotešenia za nakódenie \(j\)-teho algoritmu.

Nasledujúcich \(n\) riadkov popisuje potrebné algoritmy na vyriešenie každého z problémov,

\(i\)-ty z nich začína číslom \(k_i\) (\(0 \leq k_i \leq m\)) udávajúcim počet potrebných algoritmov pre \(i\)-ty príklad. Za ním nasleduje \(k_i\) medzerou oddelených čísel \(c_1,\dots,c_{k_i}\) (\(0 \leq c_j\leq m\)), \(j\)-te z nich znamená, že na vyriešenie problému \(i\) treba nakódiť algoritmus \(c_j\).

Formát výstupu

Na jediný riadok vypíšte maximálne potešenie, ktoré môže mačka za zadaný contest dosiahnuť. Všimnite si, že výsledok bude nezáporný.

!POZOR! výsledok sa nemusí zmestiť do bežnej celočíselnej premennej, odporúčame použiť napríklad premenné typu long long v c++.

Hodnotenie

Sú 4 sady testovacích vstupov, každá za 2 body. Pre jednotlivé sady platia nasledujúce obmedzenia:

Príklady

Input:

3 4
9 8 9
5 3 4 10
2 1 2
2 2 3
2 3 4

Output:

5

Mačka naprogramuje problémy 1 a 2, čo jej dá 17 potešenia. Na to ale musí naprogramovať algoritmy 1, 2 a 3, čo jej dá 12 antipotešenia. Spolu teda získa 5 potešenia.