ktlon

Time limit: 0.2s Memory limit: 64MB Input: ktlon.in Output: ktlon.out

Două echipe, FF și RR, formate din nn jucători fiecare, au participat în cadrul noii ediții ktlon la kk probe. După fiecare probă s-au înregistrat în registrul ktlon 2n2 \cdot n valori: primele nn reprezintă numărul de puncte câștigate în cadrul probei de jucătorii echipei FF și următoarele nn reprezintă numărul de puncte câștigate în cadrul probei de jucătorii echipei RR. Pentru ca o echipă să câștige o probă este necesar ca cel puțin unul din jucătorii săi să obțină un număr de puncte strict mai mare decât fiecare din punctajele obținute de către jucătorii celeilalte echipe. Echipa câștigătoare a probei primește un număr de stele. Pentru a stabili numărul de stele primite, mai întâi se determină numărul MM de jucători care au obținut un număr de puncte strict mai mare decât fiecare din punctajele obținute de jucătorii celeilalte echipe. Apoi echipa câștigătoare primește un număr de stele egal cu diferența dintre suma celor mai mari MM punctaje obținute de jucătorii echipei câștigătoare și suma celor mai mari MM punctaje obținute de jucătorii celeilalte echipe.

De exemplu, dacă jucătorii celor două echipe au obținut punctajele (8,5,8,3,9,7)(8, 5, 8, 3, 9, 7) și (5,7,5,4,5,1)(5, 7, 5, 4, 5, 1), atunci M=3M = 3 deoarece trei punctaje ale jucătorilor echipei FF (88, 88 și 99) sunt mai mari decât toate punctajele obținute de jucătorii echipei RR. Echipa FF câștigă proba și primește 88 stele =(9+8+8)(7+5+5)= (9 + 8 + 8) - (7 + 5 + 5). Dacă niciun jucător al niciunei echipe nu obține un număr de puncte strict mai mare decât toate punctajele obținute de jucătorii celeilalte echipe, proba se încheie cu remiză și nicio echipă nu primește nicio stea (M=0)(M = 0).

Competiția este câștigată de echipa care acumulează un număr maxim de stele la finalul tuturor probelor.

Cerință

Cunoscând nn – numărul de jucători din fiecare echipă, kk – numărul de probe și pentru fiecare probă punctajele obținute de cei 2n2 \cdot n jucători ai celor două echipe, determinați:

  1. numărul de probe câștigate de echipa RR;
  2. numărul de stele obținut de echipa câștigătoare.

Date de intrare

Fișierul de intrare ktlon.in conține pe prima linie un număr CC reprezentând cerința care trebuie să fie rezolvată (11 sau 22). Pe a doua linie se află două numere naturale nn și kk, care reprezintă numărul de jucători ai fiecărei echipe, respectiv numărul de probe, iar pe fiecare din următoarele kk linii, câte 2n2 \cdot n numere naturale: primele nn reprezintă numărul de puncte câștigate în cadrul probei curente de jucătorii echipei FF și următoarele nn reprezintă numărul de puncte câștigate în cadrul probei curente de jucătorii echipei RR. Numerele de pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Dacă C=1C = 1, fișierul de ieșire ktlon.out va conține numărul de probe câștigate de echipa RR. Dacă C=2C = 2, fișierul de ieșire va conține numărul de stele obținute de echipa câștigătoare.

Restricții și precizări

  • 1C21 \leq C \leq 2;
  • 1n10 0001 \leq n \leq 10 \ 000;
  • 1k501 \leq k \leq 50;
  • Punctajele obținute de concurenți sunt numere naturale cuprinse între 00 și 200 000200 \ 000 inclusiv.
# Punctaj Restricții
1 35 C=1C = 1
2 30 C=2C = 2 și M1M \leq 1
3 35 C=2C = 2 și M5M \leq 5

Exemplul 1

ktlon.in

1
3 4
6 8 3 7 7 6
1 2 3 4 5 3
1 5 3 4 5 2
1 5 3 4 5 2

ktlon.out

1

Explicație

Se rezolvă cerința 11. Prima probă este câștigată de echipa FF deoarece există un jucător care a obținut mai multe puncte (88) decât numărul de puncte câștigat de fiecare din jucătorii echipei RR (77, 77, 66). A doua probă este câștigată de echipa RR deoarece există doi jucători care au obținut mai multe puncte (44 respectiv 55) decât numărul de puncte câștigate de fiecare din jucătorii echipei FF (11, 22, 33). A treia probă s-a încheiat cu remiză deoarece niciun jucător al niciunei echipe nu obține un număr de puncte strict mai mare decât toate punctajele obținute de jucătorii celeilalte echipe. A patra probă s-a încheiat tot cu remiză, deoarece toți jucătorii au obținut exact aceleași punctaje ca și la proba a treia. Răspunsul este 11 deoarece echipa RR a câștigat o singură probă.

Exemplul 2

ktlon.in

2
3 3
8 8 5 7 7 7
1 2 3 3 5 3
4 1 2 6 5 1

ktlon.out

7

Explicație

Se rezolvă cerința 22. Echipa FF câștigă prima probă și primește 22 stele (M=2M = 2, (8+8)(7+7)=2(8 + 8) - (7 + 7) = 2).
Echipa RR câștigă a doua probă și primește 22 stele (M=1M = 1, 53=25 - 3 = 2). Echipa RR câștigă a treia probă și primește 55 stele (M=2M = 2, (6+5)(4+2)=5(6 + 5) - (4 + 2) = 5). În total, echipa FF a primit 22 stele iar echipa RR a primit 77 stele. Competiția este câștigată de echipa RR cu 77 stele.

Log in or sign up to be able to send submissions!