Có một tuyến xe khách đường dài nối thành phố I với thành phố O. Trên xe có một máy cấp nước cho hành khách và tài xế. Xe rời thành phố I tại thời điểm \(0\) và đến thành phố O tại thời điểm \(X\). Trên đường có \(N\) điểm tiếp nước; xe đến điểm thứ \(i\) tại thời điểm \(S_i\).

Ban đầu máy không có nước. Có thể đổ nước vào máy trước khi khởi hành và khi xe dừng tại một điểm tiếp nước. Nước có giá \(W\) yên mỗi lít tại mọi nơi.

Tại thành phố I có \(M\) hành khách lên xe, được đánh số từ \(1\) đến \(M\). Không ai lên xe ở nơi khác. Hành khách \(j\) cần một lít nước lần đầu tại thời điểm \(D_j\), rồi cứ sau mỗi \(T\) đơn vị thời gian lại cần một lít, tức tại các thời điểm \(D_j+kT\) với \(k=0,1,2,\ldots\). Ta có \(1\le D_j<T\), và \(T\) giống nhau đối với mọi người. Nếu máy hết nước khi một hành khách cần uống, người đó rời xe. Nếu hành khách \(j\) rời xe trước khi tới thành phố O, phải hoàn lại \(C_j\) yên tiền vé.

Tài xế cần một lít nước tại các thời điểm \(kT\) với \(k=0,1,2,\ldots\). Nếu máy hết nước khi tài xế cần uống, xe không thể tiếp tục hành trình.

Không có hai người cần nước cùng lúc. Khi xe đến thành phố O hoặc một điểm tiếp nước, không ai cần nước. Hãy lựa chọn lượng nước đổ vào máy để xe đến được thành phố O và tổng chi phí mua nước cùng tiền hoàn vé là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa năm số nguyên \(X,N,M,W,T\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(S_i\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(D_j,C_j\).

Dữ liệu ra

In ra một số nguyên là tổng chi phí nhỏ nhất.

Ràng buộc

• \(1\le X\le 10^{12}\).
• \(1\le N,M\le 200\,000\).
• \(1\le W\le 1\,000\,000\).
• \(1\le T\le X\).
• \(1\le S_i<X\).
• \(1\le D_j<T\).
• \(1\le C_j\le 1\,000\,000\,000\).
• Các giá trị \(D_j\) đôi một khác nhau.
• Khi xe đến thành phố O hoặc một điểm tiếp nước, không ai cần nước.

Phân nhóm

1. \(16\) điểm: \(N\le 8\), \(M\le 8\)
2. \(30\) điểm: \(N\le 100\), \(M\le 100\)
3. \(25\) điểm: \(N\le 2\,000\), \(M\le 2\,000\)
4. \(29\) điểm: Không có

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.

Ví dụ

19 1 4 8 7
10
1 20
2 10
4 5
6 5

103

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35

547

1000000000000 1 1 1000000 6
999999259244
1 123456789

333333209997456789

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 3, bài Long Distance Coach.