Kao i sve male devojčice, Katarina obožava plišane mede. Zato je na vreme počela da se priprema za Dan plišanih meda koji se održava u njenom gradiću. Na taj dan u svakoj prodavnici igračaka svaki posetilac dobija na poklon po jednog plišanog medu. Postoji n vrsta plišanih meda. Katarina je obilazila prodavnice i zaključila sledeće: Neka su prodavnice numerisane brojevima od 1 do m. Za i-tu vrstu meda postoje brojevi a_i i b_i koji govore da se taj meda prodaje u prodavnicama numerisanim brojevima iz intervala [a_i, b_i].

Pre ili kasnije, Katarina će želeti da ima po jednog medu od svake vrste. Zato ona želi da suma cena meda koje ne dobije tokom Dana plišanih meda bude što manja. Vaš zadatak je da odredite minimalnu vrednost te sume. Pretpostavlja se da Katarina svaku prodavnicu može posetiti najviše jedanput i da u prodavnici može izabrati bilo kog od meda koji se u njoj prodaju.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalazi se broj n (n ≤ 20.000), ukupan broj vrsta plišanih meda. Zatim se u narednih n redova nalaze po tri broja - u i-tom redu brojevi a_i, b_i i c_i (1 ≤ a_i ≤ b_i ≤ 2.000, c_i ≤ 10.000.000) - a_i i b_i su granice intervala brojeva prodavnica u kojima se i-ta vrsta meda prodaje, a c_i je cena te vrste. Sve cene meda su različite.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U izlaznoj datoteci treba da se nalazi samo jedan broj - minimalna moguća suma cena meda koje Katarina ne dobije tokom Dana plišanih meda.

Primer 1.

6
1 4 1
3 4 2
1 2 3
2 2 4
1 1 5
1 1 6

8

Objašnjenje.

Prvi meda se može pronaći u prodavnicama 1, 2, 3 i 4, i njegova cena je 1. Drugi meda se može pronaći u prodavnicama 3 i 4, i njegova cena je 2, itd. Jedno od rešenja je da u prodavnici 1 dobije medu 6, u prodavnici 2 medu 4, u prodavnici 3 medu 1 i u prodavnici 4 medu 2. Tada joj preostaju mede 3 i 5, njihov zbir cena je 8.

Primer 2.

2
3 10 15
15 20 25

0

Objašnjenje.

Katarina može dobiti obe vrste meda, pa kasnije neće morati da kupi nijednog medu.