Мальчик Гена очень хочет попасть на финал «Russian Code Cup», ну или хотя бы получить футболку. Но предлагаемые на отборочном раунде задачи слишком сложные, поэтому он договорился с n друзьями, что они решат задачи за него.
Участникам на отборочном раунде предлагают m задач. Про каждого своего друга Гена знает, какие задачи он умеет решать. Но друзья не согласны помогать Гене просто так: i-й друг требует за свою помощь в решении всех задач, которые он может решить, xi рублей, более того, он согласен писать код по задачам, только если к компьютеру Гены подключено не менее ki мониторов, а каждый монитор стоит b рублей.
Гена экономный, поэтому он хочет потратить как можно меньше денег на решение всех задач отборочного раунда. Подскажите Гене, как ему поступить, чтобы потратить как можно меньше денег. Считайте, что изначально у компьютера Гены нет ни одного монитора.
Выходные данные
Выведите минимальное количество денег, которое нужно потратить Гене, чтобы решить все задачи. Или выведите -1, если этого нельзя добиться.