Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ZH2014A - Բաժանիր և տիրիր

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

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

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

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

Մուտք

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

Ավելացրեց.Andreasyan
Ամսաթիվ.2014-12-23
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.Ժաուտիկովյան 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.