4. Slot machine
Gregor nedávno hral automaty v kasíne. Zaujímalo ho, koľkými spôsobmi dokáže vyhrať generačne bohatstvo. Pomôž mu!
Úloha
Herný automat sa dá vyjadriť ako 3 zoznamy čísel dĺžky $n$. Pri reálnych automatoch sú čísla pod sebou, tu sú však pre jednoduchosť vedľa seba. Každý riadok predstavuje jeden disk a pre každé číslo na ňom platí že je $\leq m$.
Jackpot nastane vtedy, keď sa tri rovnaké čísla ocitnú pod sebou v prvom stĺpci. Vypočítajte koľko rôznych jackpotov môže nastať (ako rôzny jackpot rátame rôzne otočenia diskov).
Formát vstupu
V prvom riadku vstupu je číslo $l$ udávajúce dĺžky diskov a $m$ udávajúce maximálne číslo ktoré sa môže v týchto diskoch vyskytnúť.
Nasledujú tri riadky s $l$ číslami $\leq m$ oddelenými medzerami. Platí o nich:
Obmedzenia na vstupe
| Sada | 1 | 2 | 3 |
|---|---|---|---|
| $1 \leq l \leq$ | $20$ | $1000$ | $10^4$ |
| $1 \leq m \leq$ | $3$ | $1000$ | $10^6$ |
Formát výstupu
Na jeden riadok vypíš jedno celé číslo $k$, počet možností, ktorými vie Gregor vyhrať.
Príklad
Vstup
4 11
1 2 3 11
1 1 1 1
1 3 3 1
Výstup
8
Tu môže Gregorovi padnúť generačné bohatstvo 8 rôznymi spôsobmi, vždy s jednotkami - prvý disk otočený tak ako na vstupe(bez otočenia), druhý disk môže byť otočený ľubovoľne a tretí buď vôbec alebo o jedno doprava