Điểm:
1
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một dãy gồm \(n+1\) ô xếp liên tiếp nhau từ ô \(0\) tới ô \(n\); trong đó có \(k\) ô \(A_1, A_2, \dots, A_k\) ta không thể bước chân vào (ô bị chặn).
Bạn ban đầu đứng ở ô \(0\), và bạn phải tìm cách di chuyển tới ô \(n\) bằng cách nhảy 1 ô hoặc nhảy 2 ô.
Cụ thể, nếu bạn đang ở ô \(i\), thì bạn có thể nhảy sang một trong hai ô sau, miễn là nơi bạn nhảy tới không phải là ô bị chặn và vẫn chưa nằm ngoài \(n+1\) ô:
- nhảy sang ô \(i+1\), tốn \(a\) calo
- nhảy sang ô \(i+2\), tốn \(b\) calo
Hãy tìm cách nhảy ít tốn sức nhất.
Dữ liệu đầu vào
- Dòng thứ nhất chứa hai số lần lượt là \(n\) và \(k\) \((0 \leq k \leq n \leq 10^9)\).
- Dòng thứ hai chứa hai số lần lượt là \(a\) và \(b\) \((0 \leq a, b \leq 10^9)\).
- Nếu \(k>0\), dòng thứ ba chứa \(k\) số \(A_1, A_2, \dots, A_k\) \((1 \leq A_i < n)\).
Định dạng đầu ra
In ra một số duy nhất là số calo của cách nhảy ít tốn sức nhất.
Trong trường hợp không có cách nhảy nào thỏa mãn, in ra -1.
Điểm số
- Subtask \(1\) (\(10\%\) số điểm): \(n \leq 10^9; k=0\)
- Subtask \(2\) (\(15\%\) số điểm): \(n \leq 10^5; b \geq 2a\)
- Subtask \(3\) (\(20\%\) số điểm): \(n \leq 20\)
- Subtask \(4\) (\(30\%\) số điểm): \(n \leq 10^5\)
- Subtask \(5\) (\(25\%\) số điểm): \(n \leq 10^9; k \leq 10^5\)
Ví dụ
Ví dụ
Đầu vào
7 2
2 3
1 6
Đầu ra
11
Giải thích
Ta cần ít nhất 11 calo: \(0 \xrightarrow{\text{3 calo}} 2 \xrightarrow{\text{3 calo}} 4 \xrightarrow{\text{2 calo}} 5 \xrightarrow{\text{3 calo}} 7\)
Bình luận