Rus Matryoşkaları
Rus Matryoşkalarını yəqin ki, tanıyırsınız. Bu suvenir, bir-birinin içində yerləşən çoxlu taxta matryoşkalardan ibarətdir. Kiçik ölçülü matryoşka daha böyük ölçülü matryoşkanın içində yerləşir. İndi isə bütün matryoşkaları bir-birindən ayrı yerləşdirək. Hər bir matryoşkanın xarici həcmi out[i] - onun məkanda tutduğu həcm, və daxili həcmi in[i] - onun içindəki boş məkanın həcmi var. Bir matryoşkanı digərinə yerləşdirmək mümkündür, əgər birincinin xarici həcmi ikincinin daxili həcmindən kiçikdirsə. Əgər iki və ya daha çox matryoşka birinin içindədirsə, onlar bir-birinin yanında yerləşə bilməzlər, onlar bir-birinin içində yerləşməlidirlər.
Hər bir matryoşkanın boş yerinin vahid qiyməti cost[i] məlumdur. Siz dəqiq olaraq i-ci matryoşkanın boş məkanının hər vahidi üçün cost[i] ödəməlisiniz (amma onun içindəki matryoşkalar üçün deyil). Siz matryoşkaları istədiyiniz kimi birləşdirə bilərsiniz, yalnız qaydalara zidd olmamaq şərti ilə. Tapşırıq, ümumi ödəmə dəyərini minimallaşdırmaq üçün iç-içə yerləşdirilmiş matryoşkaların belə bir kombinasiyasını tapmaqdan ibarətdir (mütləq bütün mövcud olanları deyil).
Giriş məlumatları
Birinci sətir matryoşkaların sayını n (1 ≤ n ≤ 1000) ehtiva edir. Sonrakı n sətirin hər biri i-ci matryoşkanın xarici həcmi, daxili həcmi və boş yerin qiymətini təsvir edən üç tam ədəd out[i], in[i], cost[i] (1 ≤ in[i] ≤ out[i] ≤ 1000, 1 ≤ cost[i] ≤ 1000) ehtiva edir.
Çıxış məlumatları
Bir tam ədəd p çıxarın - ödəməli olduğunuz ən kiçik dəyər.