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).

제한

힌트