29629번 - Фигурное катание 다국어

문제

На одном соревновании по фигурному катанию в 2014 году решили ввести новую систему оценки выступлений фигуристов. Каждый из $n$ элементов короткой программы было решено оценивать целым числом баллов от 0ドル$ до $a_i,ドル где $a_i$ --- максимальное число баллов, которое можно получить за $i$-ый элемент.

Общая оценка за выступление вычисляется как сумма баллов за каждый из элементов. При этом если фигурист получает за один из элементов (например, $i$-ый) менее $b_i$ баллов, то все выступление оценивается в 0ドル$ баллов.

К сожалению, члены жюри не привыкли оценивать выступление по этим правилам, поэтому они выставляют одно число $m$ --- суммарную оценку. Перед ответственным секретарем соревнований Яном стоит задача привести оценки жюри к требуемому виду, то есть получить набор чисел $c_1,ドル \dots, $c_n,ドル таких, что они удовлетворяют описанным ограничениям и оценка всего выступления равна $m,ドル или сообщить жюри, что это невозможно.

Но кроме этого Яну необходимо заполнить ведомость, поэтому ему придется воспользоваться услугами своей секретарши. За набор однозначного числа секретарша получает $x$ рублей, за набор двузначного --- $y,ドル а за набор ноля не получает ничего.

입력

В первой строке входного файла содержатся четыре целых числа: $n$ --- количество параметров, $m$ --- оценка которую хочет поставить жюри, $x$ и $y$ --- стоимость набора однозначного и двузначного числа соответственно (0ドル \le n, m, x, y \le 99$).

Следующие $n$ строк содержат по два числа $b_i$ и $a_i$ --- минимальная и максимальная оценка за $i$-ый элемент выступления (0ドル \le b_i, a_i \le 99$).

출력

В выходной файл выведите одно число --- минимально возможную суммарную стоимость выставления $m$ баллов. Если баллы выставить нельзя, выведите в выходной файл число -1.

제한

힌트