Şef

Bayramlardan əvvəl Şef bir çox bayram iclasına dəvət alır. Vaxtını daha yaxşı planlaşdırmaq üçün Şef hər bir dəvətdə iclasın davam etdiyi zaman intervalının [ a[i]; b[i] ] dəqiq göstərilməsini tələb edir. Bundan əlavə, Şef hər iclasa "əhəmiyyət" c[i] təyin edir.

Şef yarımçıq qərarları sevmir, buna görə də ya iclasda göstərilən vaxtın hamısında iştirak edir, ya da heç gəlmir. İclaslar arasında ən azı minimal fasilə olmalıdır, yəni Şef i-ci iclasdan sonra j-ci iclasa (dəvətlərin siyahısına görə) yalnız a[j] > b[i] olduqda çata bilər.

Şefə mümkün qədər böyük əhəmiyyət cəmi olan iclaslara qatılmağa kömək edəcək bir proqram yazın. Əgər eyni maksimal əhəmiyyət cəmi olan müxtəlif iclas dəstləri mümkündürsə, iclasların ümumi müddətinin daha az olduğu dəsti seçin.

Giriş məlumatları:

Proqram əvvəlcə (birinci sətirdə) tədbirlərin sayı N-i oxuyur, burada 2 ≤ N ≤ 98765, sonra isə hər biri öz sətirində olmaqla N üçlük (a[i], b[i], c[i]). Zəmanət verilir ki, 0 ≤ a[i] < b[i] < 2^31 = 2147483648, bütün c[i] təbii ədədlərdir və onların cəmi 10^9-u keçmir.

Çıxış məlumatları

Proqram seçilmiş iclasların əhəmiyyət cəmini və müddət cəmini boşluqla ayıraraq ekrana çıxarmalıdır.