34583번 - Zečevi 서브태스크다국어

Na brojevnom pravcu nalazi se $N$ zečeva, $i$-ti zec se nalazi na poziciji $x_i$ te na početku ima $p_i$ energije. Svake sekunde događa se sljedeće: ako svi zečevi imaju bar jednu jedinicu energije, skaču za jedno mjesto u desno te potroše jednu jedinicu energije. Ako barem jedan zec ima nula energije, svi prestaju skakati zauvijek.

Mrkve. Mrkve su također na istom brojevnom pravcu, $i$-ta mrkva se nalazi na poziciji $y_i$ i teška je $t_i$ kilograma. Kad zec dođe na poziciju gdje se nalazi mrkva, može pojesti $a$ kilograma te mrkve, gdje je a cijeli broj između $0$ i težine te mrkve. Nakon toga tom zecu se poveća energija za $a$, a težina te mrkve se smanji za $a$ kilograma.

Odredite koliko najviše sekundi zečevi mogu skakati, ukoliko na optimalan način jedu mrkve.

U prvom retku su prirodni brojevi $N$ i $M$, broj zečeva i broj mrkvi.

U sljedećih $N$ redaka nalaze se po dva broja. U $i$-tom od tih redaka nalaze se brojevi $x_i$ i $p_i$ , početna pozicija i energija $i$-tog zeca.

U sljedećih $M$ redaka nalaze se po dva broja. U $i$-tom od tih redaka nalaze se brojevi $y_i$ i $t_i$, pozicija i početna težina $i$-te mrkve.

Ispišite koliko najviše sekundi zečevi mogu skakati.

Pojašnjenje prvog probnog primjera:

Nakon prva tri skoka zečevi imaju energije redom $1$, $0$ i $2$. Drugi zec se sada nalazi na poziciji na kojoj je mrkva težine $2$ pa ju može cijelu pojesti, čime njegova energija postaje $2$. Zečevi sada opet mogu napraviti jedan skok, nakon čega im energije postaju $0$, $1$ i $1$. Prvi zec se sada nalazi na poziciji $6$ na kojoj je mrkva težine $3$. Nakon jedenja mrkve zečevi imaju težine $3$, $1$ i $1$ pa mogu napraviti još jedan skok. Ukupan broj napravljenih skokova je pet. Moguće je pokazati da je nemoguće postići da zečevi naprave šest skokova.