Вася находится в центре проката машин и хочет как можно скорее добраться до кинотеатра. Сеанс, на который он уже купил билет, начнётся через t минут. Считайте, что есть прямая дорога от центра проката машин до кинотеатра длиной s километров. Введём систему координат так, что центр проката машин находится в точке 0, а кинотеатр находится в точке s.
Известно, что по пути от центра проката машин до кинотеатра есть k заправочных станций, причём на всех можно заливать неограниченное количество топлива совершенно бесплатно! Считайте, что операция залива топлива осуществляется мгновенно.
В центре проката есть n машин, i-я из которых характеризуется двумя числами ci и vi — стоимостью аренды машины и вместимостью её бака. Таким образом, на заправке нельзя заливать в машину топлива больше вместимости её бака vi. В центре проката все машины изначально полностью заправлены.
Каждая из машин может ехать в одном из двух скоростных режимов: обычном и ускоренном. В обычном режиме машина проезжает 1 километр за 2 минуты, при этом тратит на это 1 литр топлива. В ускоренном режиме машина проезжает 1 километр за 1 минуту, при этом тратит на это 2 литра топлива. Режим может быть изменён в любой момент. Изменять режим разрешается неограниченное количество раз.
Перед вами стоит задача выбрать машину с минимальной стоимостью аренды, на которой Вася успеет добраться до кинотеатра до начала своего сеанса, то есть не позднее, чем через t минут. Считайте, что в центре проката все машины изначально полностью заправлены.
Выходные данные
Выведите минимальную стоимость аренды подходящей машины, то есть такой, что Вася успеет добраться до кинотеатра до начала сеанса (не позднее, чем через t минут). Если ни одна из машин не подойдёт Васе, выведите -1.
Примечание
В первом примере Вася успеет доехать до кинотеатра вовремя на первой и третьей машине, но выгоднее поехать на первой, стоимость аренды которой равна 10, а объём топливного бака равен 8. Тогда до первой заправки Вася сможет доехать в ускоренном режиме за 3 минуты, потратив на это 6 литров топлива, а затем, заправив полный бак, он сможет проехать 2 километра в обычном режиме за 4 минуты, потратив на это 2 литра бензина. Оставшиеся 3 километра он проедет в ускоренном режиме за 3 минуты, потратив на это 6 литров бензина.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 8 10
10 8
5 7
11 9
3
|
10
|
|
2
|
2 2 10 18
10 4
20 6
5 3
|
20
|