피겨 스케이팅

2014년 한 피겨스케이팅 대회에서 선수의 연기를 채점하는 새로운 방식을 도입하기로 했다. 쇼트 프로그램의 $n$개 요소는 각각 $0$에서 $a_i$ 사이의 정수로 채점된다. 여기서 $a_i$는 $i$번째 요소의 최고 점수이다.

총점은 각 요소 점수의 합이다. 다만 어떤 요소 $i$에서 선수가 $b_i$점 미만을 받으면 연기 전체가 $0$점으로 처리된다.

심사위원들은 이 규칙에 따른 채점에 익숙하지 않아서 합계 점수 $m$이라는 숫자 하나만 적었다. 대회 책임 간사 얀은 심사위원의 점수를 규칙에 맞는 형태로 고쳐야 한다. 즉 위의 제약을 모두 만족하면서 합이 $m$이 되는 수열 $c_1, \dots, c_n$을 찾거나, 그럴 수 없다고 알려야 한다.

얀은 성적표도 작성해야 하며, 이를 위해 비서를 쓴다. 비서는 한 자리 수를 입력하면 $x$루블, 두 자리 수를 입력하면 $y$루블을 받는다. 0을 입력하면 아무것도 받지 않는다.

첫 줄에 정수 네 개 $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을 출력한다.