25136번 - Još jači 다국어

Jednom davno u dalekoj zemlji živio je car Malnar koji je volio ratovati. Ostala su se kraljevstva udružila protiv njega i s jednom velikom vojskom krenula u napad na njegov dvorac.

Jedini je put do dvorca dugačka staza, uz koju je postavljeno $n$ tornjeva. Na tom putu, $i$-ti toranj vidi interval od $l_i$ do $r_i$ te se na njemu nalazi $p_i$ strijelaca. Svaki strijelac može u jednoj sekundi pogoditi jednog vojnika.

Stazom prolazi velika vojska koja se sastoji od $k$ vojnika. Vojska prelazi jedan metar u sekundi. Primjerice, ako vojska naiđe na toranj koji nadzire područje od $2$ do $5$ i na njemu se nalazi jedan strijelac, on će pogoditi $3$ vojnika prije nego što vojska izađe iz njegovog vidokruga. U blizini svakog tornja nalazi se i selo. U $i$-tom selu nalazi se $s_i$ seljaka koji su voljni pomoći i svi zajedno postati strijelci i-tog tornja za $c_i$ zlatnika. Car Malnar je pohlepan velikodušan i želi potrošiti što manje zlatnika kako bi porazio protivničku vojsku. Pomozite mu!

U prvom su retku prirodni brojevi $n$ ($1 ≤ n ≤ 1\,000$) i $k$ ($1 ≤ k ≤ 10\,000$) iz teksta zadatka.

U sljedećih $n$ redaka nalaze se prirodni brojevi $l_i$, $r_i$, $p_i$ ($1 ≤ l_i , r_i , p_i ≤ 1\,000$, $l_i < r_i$), koji redom predstavljaju lijevu i desnu granicu vidokruga $i$-tog tornja, te broj strijelaca na $i$-tom tornju. Intervali tornjeva mogu se preklapati.

U sljedećih $n$ redaka nalaze se prirodni brojevi $s_i$, $c_i$ ($1 ≤ s_i ≤ 1\,000$, $1 ≤ c_i ≤ 10^5$), koji označavaju da $i$-tom tornju za $c_i$ zlatnika može pomoći $s_i$ seljaka.

U prvom i jedinom retku potrebno je ispisati koliko je minimalno zlata potrebno potrošiti da se porazi protivnička vojska. Ako vojsku nikako nije moguće poraziti ispišite "PREDAJA" (bez navodnika).