eolymp
bolt
Try our new interface for solving problems

Avtobus

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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ə

Giriş verilənləri #1
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Çıxış verilənləri #1
4
Mənbə 2000 XIII All-Ukrainian Informatics Olympiad, Kiev, March 27 - April 1, Round 1