Piroqların acgözlüklə yeyilməsi

Fermər Conun $m$ inəyi var, $1$-dən $m$-ə qədər nömrələnmiş, və bu inəklər zaman-zaman ot yeməyini dəyişməyi sevirlər. Xüsusi bir ləzzət olaraq, fermər Con $n$ piroq bişirib, $1$-dən $n$-ə qədər nömrələnmiş. İnək $i$ [l_i, r_i] (daxil olmaqla) aralığında olan piroqları sevir və hər bir inəyin sevdiyi piroqların aralığı unikaldır. Bundan əlavə, hər bir inək $i$-nin $1$-dən 10^6-a qədər olan tam ədədlə ifadə olunan çəkisi w_i var.

Fermər Con inəklərin c_1, c_2, ..., c_k ardıcıllığını seçə bilər, hansı ki, onlar bu sırayla növbə ilə yeyəcəklər. Lakin inəklər paylaşmağı bacarmırlar! İnək c_i-nin növbəsi gəldikdə, o, sevdiyi bütün piroqları, yəni [l_{c_i}, r_{c_i}] aralığında qalan bütün piroqları yeyir. Fermər Con inəyin növbəsi gəldikdə, onun üçün heç bir sevdiyi piroq qalmadığı utancverici vəziyyətdən qaçmaq istəyir. Buna görə də, o, hər bir inəyin bu ardıcıllıqda ən azı bir piroq yediyi c_1, c_2, ..., c_k ardıcıllığının mümkün olan maksimum ümumi çəkisini (w_{c_1} + w_{c_2} + ... + w_{c_k}) hesablamalıdır.