Državno natjecanje 2020. godine za 1. i 2. razred Srednje Škole - 1. zadatak

Dječji vrtić “Tikvice” ogranizira priredbu za svoje mališane i za nju će naručiti neki broj balona. Djeca su se složila oko toga da baloni budu crvene i plave boje, jedino se mišljenja o broju crvenih i broju plavih balona razilaze. Stoga su tete u ovom vrtiću odlučile provesti anketu među djecom da saznaju koliko balona koje boje valja naručiti. Anketa je provedena na način da je svako od ukupno n djece izreklo dvije rečenice sljedećeg oblika:

1. Crvenih balona treba biti barem c1, a najviše c2.
2. Plavih balona treba biti barem p1, a najviše p2.

Pomozite tetama ovog vrtića i izračunajte na koliko je načina moguće naručiti balone (tj. odabrati broj crvenih i broj plavih balona) tako da svakom djetetu barem jedna od dvije rečenice koje je izreklo bude cijela ispunjena. Pritom broj balona svake boje mora biti cijeli broj između 0 i zadanog prirodnog broja m (uključivo).

ULAZNI PODACI

U prvom su retku prirodni brojevi n (1 ≤ n ≤ 300 000) i m (2 ≤ m ≤ 10^9), broj djece i maksimalan broj balona svake boje.

Svaki od sljedećih n redaka opisuje zahtjeve jednog djeteta, kao četvorku cijelih brojeva c1, c2, p1, p2 (0 ≤ c1 ≤ c2 ≤ m, 0 ≤ p1 ≤ p2 ≤ m).

IZLAZNI PODACI

U jedini redak ispišite traženi broj načina (koji može iznositi i 0, ako nije moguće zadovoljiti uvjete).

PRIMJERI TEST PODATAKA

ulaz

2 5
1 2 3 4
0 5 0 5

izlaz

20

ulaz

3 3
2 3 1 1
1 2 2 3
2 2 0 2

izlaz

6

ulaz

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

izlaz

47

Objašnjenje drugog primjera: ispravni odabiri broja crvenih i plavih balona su (1, 1), (2, 0), (2, 1), (2, 2), (2, 3) i (3, 2).