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 \textbf{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. \InputFile Birinci sətirdə: dayanacaqların sayı \textbf{N }və avtobusdakı yerlərin \textbf{M} sayı verilir. Sonrakı \textbf{N} sətrin \textbf{i}-cisində, \textbf{i}-ci və \textbf{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 \textbf{i+1}-ci dayanacaqdır). \textbf{1≤ M≤ 2000, 1 ≤ N, K ≤ 200000} olması məlumdur. \OutputFile Maksimal sayda işçi aparmaq üçün tələb olunan minimal vaxtı verməli.