Летом Петя Торопыжкин в составе компании из \(n\) друзей поучаствовал в мотопробеге в Европу (каждый участник ехал на своём мотоцикле). К концу одного из дней пробега, когда пришло время вставать на ночёвку, они были на платной дороге, состоящей из \(l\) отрезков. Для \(i\)-го участника пробега известен номер \(x_i\) отрезка дороги, на котором он находится. Стоимость проезда по \(k\)-му отрезку равна \(d_k\), не зависит от направления проезда и взимается при въезде на этот отрезок; дальнейшее движение по отрезку не требует затрат. Во время подготовки к поездке было выяснено, что на этой дороге имеется \(m\) мотелей. Мотель с номером \(j\) расположен на отрезке дороги с номером \(y_j\) (на одном участке дороги может быть один мотель, несколько мотелей или не быть вовсе) и может вместить \(p_j\) постояльцев. Общая вместимость всех мотелей достаточна, чтобы все друзья могли заночевать под крышей. По имеющимся данным нужно определить минимальные затраты на дорожные сборы, чтобы каждый из друзей доехал до какого-нибудь мотеля.