SPOJ in Armenian

Մանսուրը նոր ստրատեգիական խաղ է խաղում։ Այդպիսի խաղերում ամենագլխավոր խնդիրներից մեկը ռեսուրսների ձեռքբերումն է։ Բարեբախտաբար այդ խաղում զարգացման համար միայն մեկ ռեսուրս է անհրաժեշտ՝ դա ոսկին է, և մեկ օժանդակ՝ էներգիա։

Խաղում գոյություն ունեն հանքեր, որտեղ արդյունահանվում են ոսկու և էներգիայի որոշակի պաշարներ։ Բոլոր հանքերը գտնվում են մի ուղղի վրա։ Սեփական հանքերը պաշտպանելու համար կարելի է կառուցել ուժային դաշտ (հանքերը ծածկող հատված տրված ուղղի վրա, ընդ որում ծայրակետերը ներառյալ են), որը ծախսում է իր երկարությանը հավասար էներգիա։

Մանսուրը ցանկանում է կառուցել մի ուժային դաշտ այնպես, որ այդ դաշտի հանքերից արդյունահանված էներգիան բավարար լինի ուժային դաշտին էներգիա մատակարարելու համար, իսկ ոսկին, որքան հնարավոր է շատ լինի։

Օգնեք Մանսուրին, գրեք ծրագիր, որը պարզի, թե նա առավելագույնը որքան ոսկի է կարող հանել պաշտպանված հանքերից։

Մուտք

Առաջին տողում տրված է հանքերի N (1<= N <= 100000) քանակը։ Հաջորդ N տողերից յուրաքանչյուրը պարունակում է երեք ամբողջ  xi, gi, di թվեր (0 <= xi <= 10⁹, 1 <= gi <=10⁹, 1 <= di <= 10⁹), որոնք ցույց են տալիս հանքի կոորդինատը, արդյունահանվող ոսկու քանակը և էներգիայի քանակը, համապատասխանաբար։ Բոլոր  xi-երը տարբեր են և տրված են աճման կարգով։

Ելք

Արտածեք մեկ թիվ՝ ոսկու առավելագույն քանակը, որ Մանսուրը կարող է խաղում արդյունահանել։

Օրինակներ

Մուտք.
4
0 5 1
1 7 2
4 4 1
7 15 1

Output:
16

Input:
2
0 4 1
3 5 1

Ելք
5