Иннополис에서 열리는 2224년 전러시아 정보 올림피아드에서는 자신을 복제할 수 있는 차세대 로봇이 배달을 담당한다. 집 밖으로 나가지 않고도 창문을 통해 바로 배달을 받을 수 있다.

처음에는 배달 로봇이 한 대만 있다. 언제든지 가장 위에 있는 로봇은 자신의 바로 위에 새로운 로봇을 한 대 이상 만들 수 있다. 이렇게 로봇들이 수직으로 쌓인 기둥이 만들어진다. 각 로봇의 높이는 한 층의 높이와 같다.

배달하는 동안 동일한 복제 로봇들로 이루어진 기둥은 기숙사 건물을 따라 왼쪽에서 오른쪽으로 이동한다. 로봇들의 데이터베이스에는 접수된 주문 목록이 있으며, 각 주문에 대해 배달해야 하는 창문이 알려져 있다. 로봇 기둥이 어떤 주문에 해당하는 창문을 지나갈 때, 그 창문과 같은 높이에 있는 로봇이 기둥에 있다면 배달할 수 있다.

이동하는 동안 로봇 구조물이 장애물에 부딪힐 수 있다. 장애물을 지난 뒤에는 장애물보다 위에 있던 로봇들만 계속 이동한다. 이 로봇들은 장애물 바로 뒤의 지면에 내려오며, 여전히 수직 기둥 형태를 유지한다. 이후에도 이동하고, 새로운 복제 로봇을 만들고, 주문을 배달할 수 있다.

장애물과 창문 사이의 거리는 충분히 멀기 때문에 로봇들이 장애물을 통과하는 동안 창문을 지나가는 일은 없다.

배달을 운영하는 회사는 주문 하나를 배달할 때마다 $p$ 크립토루블을 받는다. 새로운 로봇 한 대를 만드는 비용은 $c$ 크립토루블이다. 최종 이익은 주문 배달로 얻은 총수입에서 모든 로봇을 만드는 데 든 총비용을 뺀 값이다. 회사는 이익을 최대화하려고 한다. 모든 주문을 배달할 필요는 없으며, 로봇들은 언제든지 멈추고 배달 과정을 종료할 수 있다.

회사가 얻을 수 있는 최대 이익을 구하여라.

입력

첫 번째 줄에는 네 정수 $n$, $m$, $c$, $p$가 주어진다 ($0 \le n,m \le 100000$, $1 \le c,p \le 10^6$). 각각 장애물의 수, 데이터베이스에 있는 주문의 수, 복제 로봇 한 대를 만드는 비용, 주문 하나를 배달하고 받는 금액이다.

다음 $n+m$개의 줄에는 장애물과 주문을 배달해야 하는 창문에 대한 설명이 로봇 기둥이 기숙사를 따라 왼쪽에서 오른쪽으로 이동하면서 만나는 순서대로 주어진다. 각 줄에는 두 정수 $t_i$와 $h_i$가 주어진다 ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$). $t_i$는 물체의 종류로, $1$은 장애물이고 $2$는 창문이다. $h_i$는 층 단위로 나타낸 장애물의 높이 또는 창문이 있는 층이다.

종류가 $1$인 물체는 정확히 $n$개이고, 나머지 $m$개의 물체는 종류가 $2$임이 보장된다.

출력

얻을 수 있는 최대 이익을 나타내는 수 하나를 출력하여라.

서브태스크

예제

입력 1

2 3 2 6
1 2
2 3
1 1
2 6
2 2

출력 1

4

입력 2

1 3 1 5
2 2
2 1
1 9
2 1

출력 2

9

참고

첫 번째 예제에서 주문을 배달하는 최적 전략 중 하나가 아래의 아홉 그림에 나타나 있다. 이때 두 번째 주문을 배달하더라도 이익은 증가하지 않는다.

두 번째 예제에서는 첫 번째 주문을 배달하기 위해 로봇을 한 번 복제하고, 그렇게 만들어진 로봇 구조물로 두 번째 주문을 배달하면 충분하다. 세 번째 주문을 배달하기 위해 추가로 복제하는 것은 경제적으로 이득이 없다.