Новогодние праздники в Берляндии длятся n дней. Только вот снегом зима в этом году не порадовала, поэтому организаторы зимних праздничных мероприятий вынуждены закупать искусственный снег. В Берляндии есть m фирм, продающих снег. Каждый день i-я фирма производит w_i кубометров снега. На следующий день снег тает и фирма вынуждена производить w_i кубометров снова. Во время праздников действуют новогодние скидки, поэтому каждый день стоимость снега уменьшается. Известно, что в первый день стоимость всего снега, произведенного i-й фирмой, составляет c_i бурлей. Каждый день эта общая стоимость уменьшается на a_i бурлей, т.е. во второй день она равна c_i - a_i, в третий день — c_i - 2a_i, и т. д. Известно, что ни для одной фирмы стоимость производимого ей снега не становится отрицательной или равной нулю. Вам требуется организовать закупку снега таким образом, чтобы каждый день покупать ровно W кубометров снега. При этом у любой фирмы не обязательно покупать весь снег, произведенный ею. Если вы покупаете у i-й фирмы в один из дней, когда стоимость ее снега равна s_i, n_i кубометров снега (0 ≤ n_i ≤ w_i, число n_i не обязательно целое!), то его цена составит бурлей. В течение одного дня можно покупать снег у нескольких фирм. В разные дни можно покупать снег у разных фирм. Требуется сделать закупки таким образом, чтобы потратить как можно меньше денег. Гарантируется, что производимого фирмами снега будет достаточно.