Državna razina / Primjena algoritama OŠ 2022. / Osnovna škola (7. razred / 8. razred) - 3. zadatak / 2. zadatak

Lovro i Domagoj ispunili su svoj dugogodišnji san i zajednički otvorili teretanu. Trenutno rade poslovni plan za sljedećih K dana. Trenutno imaju N redovnih posjetitelja, te za svakog posjetitelja znaju kolika mu je težina potrebna za trening i koje će dane dolaziti u teretanu. Naime, u svojoj teretani imaju A utega po 1.25 kg, B utega po 2.5 kg, C utega po 5 kg, D utega po 10 kg i E utega po 20 kg. Ako sljedećih K dana označe brojevima od 1 do K, znaju da će i-ti posjetitelj dolaziti od Li-tog dana do Ri-tog dana te će mu svaki dan biti potrebna težina od točno Ti kg. Sada su Lovro i Domagoj u problemu, jer ne znaju na koje će dane moći zadovoljiti sve svoje posjetitelje te su tebe zamolili da napraviš program koji izračunava koliko će dana uspjeti dati svakom posjetitelju traženu težinu.

Ulazni podaci

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 100000) i K (1 ≤ K ≤ 100000) iz teksta zadatka. U drugom se retku nalaze prirodni brojevi A, B, C, D i E (1 ≤ A, B, C, D, E ≤ 2000000). U sljedećih se N redaka nalaze dva prirodna broja Li i Ri (1 ≤ Li ≤ Ri ≤ 100000) te realni broj Ti (0 ≤ Ti ≤ 1000) s dvije decimale označene decimalnom točkom.

Izlazni podaci

Ispiši broj dana na koje će Lovro i Domagoj uspjeti zadovoljiti sve posjetitelje.

Bodovanje

U primjerima vrijednim 18 bodova vrijedit će da je N=1, K ≤ 100, C = 0, D = 0, E = 0. U primjerima vrijednim dodatnih 36 bodova vrijedit će N=1, K ≤ 100. U primjerima vrijednim dodatnih 18 bodova vrijedit će K=1.

Primjer zadatka

Ulaz

3 1
1 2 1 1 1
1 1 20.00
1 1 23.75
1 1 40.00

Izlaz

0

Ulaz

5 3
3 6 10 11 5
1 3 47.50
2 3 38.75
1 2 26.25
1 2 56.25
2 3 11.25

Izlaz

2

Ulaz

4 2
3 1 6 1 0
2 2 53.75
2 2 25.00
1 2 18.75
2 2 5.00

Izlaz

1

Opis drugog probnog primjera:

Lovro i Domagoj mogu zadovoljiti posjetitelje prvog i trećeg dana. Prvog dana će dati prvom posjetitelju tri utega od 2.5 kg i dva utega od 20 kg, trećem posjetitelju jedan od 1.25 kg, pet od 5 kg, četvrtom jedan od 1.25 kg., tri od 5 kg i dva od 20 kg. Treći dan će dati prvom posjetitelju jedan od 2.5 kg, jedan od 5 kg i četiri utega od 10 kg, drugom posjetitelju jedan od 1.25 kg, jedan od 2.5 kg i jedan od 5 kg, jedan od 10 kg, jedan od 20 kg, a petom jedan od 1.25 kg i dva od 5 kg.