Bạn là huấn luyện viên của một đội bóng đá danh tiếng trong giải JOI. Đội có \(N\) cầu thủ, đánh số từ \(1\) đến \(N\). Sân là hình chữ nhật cao \(H\) mét theo hướng bắc-nam và rộng \(W\) mét theo hướng đông-tây. Điểm \((i,j)\) cách góc tây bắc \(i\) mét về phía nam và \(j\) mét về phía đông.

Khi bắt đầu thu dọn sau buổi tập, cầu thủ \(i\) đứng tại \((S_i,T_i)\). Chỉ có một quả bóng và cầu thủ \(1\) đang giữ bóng. Bạn đứng cùng cầu thủ \(N\) tại \((S_N,T_N)\). Việc thu dọn kết thúc khi bóng được đưa tới \((S_N,T_N)\) và bạn bắt được bóng. Bạn không di chuyển.

Mỗi hành động làm tăng mức mệt mỏi của cầu thủ thực hiện:

1. Nếu đang giữ bóng, cầu thủ chọn một trong bốn hướng và số nguyên dương \(p\), rồi sút bóng đúng \(p\) mét theo hướng đó. Cầu thủ đứng yên, mất quyền giữ bóng và tăng mệt mỏi thêm \(A\times p+B\).
2. Cầu thủ chọn một trong bốn hướng và di chuyển \(1\) mét. Nếu đang giữ bóng, cầu thủ mang bóng theo. Mức mệt mỏi tăng thêm \(C\).
3. Nếu đang giữ bóng, cầu thủ đặt bóng tại vị trí hiện tại và mất quyền giữ bóng. Mức mệt mỏi không đổi.
4. Nếu không ai giữ bóng, cầu thủ đứng cùng vị trí với bóng có thể nhặt bóng. Mức mệt mỏi không đổi.

Cầu thủ và bóng được phép ra ngoài sân; nhiều cầu thủ có thể đứng cùng một vị trí. Hãy tính tổng mức mệt mỏi nhỏ nhất để đưa bóng cho bạn.

Dữ liệu vào

• Dòng đầu chứa \(H,W\).
• Dòng thứ hai chứa \(A,B,C\).
• Dòng thứ ba chứa \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(S_i,T_i\).

Dữ liệu ra

In tổng mức mệt mỏi nhỏ nhất có thể.

Ràng buộc

• \(1\le H,W\le 500\).
• \(0\le A,B,C\le 1\,000\,000\,000\).
• \(2\le N\le 100\,000\).
• \(0\le S_i\le H\) và \(0\le T_i\le W\).
• \((S_1,T_1)\ne(S_N,T_N)\).

Phân nhóm

1. \(5\) điểm: \(N=2\)
2. \(30\) điểm: \(N\le 1\,000\) và \(A=0\)
3. \(65\) điểm: Không có ràng buộc bổ sung

Ví dụ

6 5
1 3 6
3
1 1
0 4
6 5

26

3 3
0 50 10
2
0 0
3 3

60

4 3
0 15 10
2
0 0
4 3

45

4 6
0 5 1000
6
3 1
4 6
3 0
3 0
4 0
0 4

2020

Nguồn

JOI 2016/2017, Vòng chung kết.