Avtobus
Avtobus
Xidməti avtobus təyin olunmuş marşrut üzrə hərəkət edərək boş yeri olduqca dayanacaqlarda gözləyən və hələ dayanacağa çatmamış olan işçiləri də gözləməklə yığaraq zavoda aparır. Hər işçinin öz dayanacağına gəlməsi vaxtı və avtobusun bütün dayanacaqlararası məsafələri qət etmə müddətləri məlumdur. Avtobusun birinci dayanacaqdan hərəkətə başlama vaxtı və işçinin avtobusa minməyə sərf etdiyi müddət sıfır hesab olunur.
Avtobusun zavoda mümkün qədər çox sayda işçi aparması üçün tələb olunan minimal vaxtı təyin etmək üçün proqram yazın.
Giriş verilənləri
Birinci sətirdə: dayanacaqların sayı N və avtobusdakı yerlərin M sayı verilir. Sonrakı N sətrin i-cisində, i-ci və i+1-ci dayanacaqlar arasındakı məsafəyə sərf olunan zaman, həmin dayanacağa gələn işçilərin k sayı və onların oraya gəlmə vaxtı ardıcıl olaraq tam ədədlər olaraq qeyd olunur (zavod i+1-ci dayanacaqdır). 1≤ M≤ 2000, 1 ≤ N, K ≤ 200000 olması məlumdur.
Çıxış verilənləri
Maksimal sayda işçi aparmaq üçün tələb olunan minimal vaxtı verməli.
Nümunə
3 5 1 2 0 1 1 1 2 1 4 0 2 3 4
4