LQDOJ CUP 2023 - Round 8

Cho một dải ô gồm \(10^9\) ô vuông liên tiếp, trong đó có \(n\) ô chưa được sơn màu và những ô còn lại đã được sơn. Một cây cọ sơn kích thước \(w\) có thể quét sơn cho \(w\) ô liên tiếp, cụ thể là nếu chọn \(x\) (\(1 \leq x \leq 10^9\)) là vị trí bắt đầu thì cây cọ có thể quét sơn toàn bộ các ô liên tiếp từ vị trí \(x\) đến \(x + w - 1\) (có thể quét ra ngoài, không ảnh hưởng đến bài toán).

Bạn đang lên kế hoạch để sơn hết các ô chưa được sơn. Bạn dự định mua \(a\) cây cọ sơn kích thước \(w\) và \(b\) cây cọ sơn kích thước \(2 \times w\), mỗi cây cọ sẽ được dùng để sơn nhiều nhất một lần và mỗi ô có thể được sơn nhiều lần. Nhưng cây cọ có kích thước càng lớn thì giá cả lại càng cao, vì vậy bạn muốn tìm giá trị \(w\) nhỏ nhất có thể. Hãy tìm giá trị \(w\) đó.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(a\) và \(b\) \((1 \leq n \leq 2000, 0 \leq a, b \leq 10^9, a + b \geq 1)\) lần lượt là số ô chưa được tô màu, số cây cọ sơn kích thước \(w\) và \(2 \times w\).
• Dòng tiếp theo chứa \(n\) số nguyên phân biệt \(x_1, x_2, \ldots, x_n\) \((1 \leq x_i \leq 10^9)\) là vị trí của những ô chưa được sơn.

Output

• Một số nguyên duy nhất là giá trị \(w\) nhỏ nhất để có thể sơn hết những ô chưa được sơn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Các ô chưa được sơn đứng cạnh nhau.
• Subtask \(2\) (\(20\%\) số điểm): \(b = 0\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 200\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 1 1
1 2 3 4 5

2

7 3 0
1 3 4 5 7 9 10

4

Huy là một học sinh có nhiều hứng thú về đồ thị. Trong quá trình nghiên cứu về chủ đề này, Huy đã nghĩ ra một dạng đồ thị dựa trên tên anh ấy, gọi là đồ thị H. Một đồ thị H là một đồ thị vô hướng gồm \(6\) đỉnh phân biệt được kí hiệu lần lượt là \(A, B, C, D, E, F\) và \(5\) cạnh:

• \(C\) có cạnh nối với \(A, B\);
• \(D\) có cạnh nối với \(E, F\);
• \(C\) và \(D\) có cạnh nối với nhau.

Là một người cùng nghiên cứu đồ thị với Huy, bạn được Huy cho một đồ thị \(G\) vô hướng gồm \(n\) đỉnh và \(m\) cạnh sao cho mỗi cạnh nối hai đỉnh khác nhau và giữa hai đỉnh bất kỳ có tối đa một cạnh nối giữa chúng. Nhiệm vụ của bạn là giúp Huy đếm xem có bao nhiêu đồ thị con khác nhau của \(G\) thỏa mãn điều kiện của một đồ thị H.

Biết rằng:

• Đồ thị con của đồ thị \(G=(V,E)\) là đồ thị \(H=(W,F)\), sao cho \(W \subseteq V\) và \(F\subseteq E\).
• Hai đồ thị con được gọi là khác nhau khi tồn tại cạnh xuất hiện trong đồ thị này nhưng không xuất hiện trong đồ thị còn lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \(\left(1 \leq n \le 10^5, 0 \leq m \le \min\left(\frac{n \times (n-1)}{2}, 4 \times 10^5\right)\right)\) lần lượt là số đỉnh và số cạnh của đồ thị.
• Trong \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \le u \neq v \le n)\) cho biết có một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

• Một số nguyên duy nhất là số lượng đồ thị con của \(G\) là đồ thị H sau khi chia lấy dư cho \(10^9+7\).

Example

6 7
1 2
2 3
3 4
4 5
5 6
6 1
6 3

1

6 9
1 2
2 3
3 4
4 5
5 6
6 1
6 3
3 5
2 4

2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(m = n - 1\) và giữa hai đỉnh bất kỳ đều tồn tại đường đi giữa chúng.
• Subtask \(3\) (\(20\%\) số điểm): \(n, m \leq 5000\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^{4}\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Sóc vừa hái những quả sầu riêng giúp mẹ xong nên đã đến lúc về nhà. Sóc đang đứng ở vị trí \(0\) và đi một đường thẳng về nhà ở vị trí \(h\) với khoảng cách là \(h\) mét, được biết khi đi mỗi giây sóc đi được đúng \(1\) mét, có thể biểu diễn trên trục \(Ox\) với vị trí sóc đang đứng là gốc tọa độ \(x = 0\) còn nhà sóc ở vị trí \(x = h\).

Tuy nhiên đường đi không thuận lợi như sóc nghĩ, mỗi \(1\) giây sóc làm rơi \(1\) quả sầu riêng, và cứ \(t\) giây từ khi bắt đầu sóc bị lại trộm mất \(g\) quả. Nhưng may thay, có \(q\) trạm bảo vệ ở trên đường lần lượt ở các vị trí: \(a_{1}, a_{2}, \ldots, a_{q}\) và vị trí \(0\) luôn là trạm bảo vệ \((a_{1} = 0)\). Sóc có thể dừng lại nghỉ ngơi tại các trạm bảo vệ với số giây bất kỳ (số giây phải là số nguyên), tuy nhiên không được dừng tại bất kỳ vị trí nào khác. Tại các trạm bảo vệ sóc sẽ không bị trộm mất sầu riêng ở bất kỳ thời gian nào nhưng vẫn bị rơi sau mỗi giây. Ngoài ra, nhà của sóc cũng giống như trạm bảo vệ nên khi ở trong nhà sóc cũng sẽ không bị trộm. (Xem phần giải thích ví dụ để hiểu rõ hơn)

Hãy giúp sóc về đến nhà mà bị mất ít quả sầu riêng nhất nhé, được biết túi sóc đựng một số lượng sầu riêng rất lớn và không thể nào bị rớt và trộm hết.

Input

• Dòng đầu tiên chứa bốn số nguyên \(h\), \(t\), \(g\) và \(q\) \((1 \leq t < h \leq 10^{12}, 1 \leq g \leq 10^6, 1 \leq q \leq \min(h, 10^5))\), với \(h\) là vị trí nhà của sóc, và cứ \(t\) giây thì nếu sóc không ở trong trạm bảo vệ thì bị mất \(g\) quả và cuối cùng là \(q\) là số lượng trạm trú ẩn.
• Dòng tiếp theo chứa \(q\) số nguyên \(a_{1}, a_{2}, \ldots, a_{q}\) \((0 = a_{1} < a_{2} < \ldots < a_{q} < h)\) là các trạm trú ẩn.

Output

• Một số nguyên duy nhất là số quả sầu riêng mà sóc làm rơi và bị trộm mất là ít nhất.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(t \le 10^6\) và \(q = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(h \le 10^3\).
• Subtask \(3\) (\(25\%\) số điểm): \(t \le 10^6\) và \(q \le 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): \(t \le 10^2\).
• Subtask \(5\) (\(15\%\) số điểm): \(t \le 10^5\).
• Subtask \(6\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

18 4 5 3
0 8 15

Output

29

Note

• Ở cách này, sóc đi một mạch mà không dừng ở bất kỳ đâu hết \(18\) giây nên bị rớt mất \(18\) quả và ở giây thứ \(4, 12, 16\) sóc không ở trong trạm bảo vệ nên sóc bị trộm mất \(3 \times g = 15\) quả nữa. Vậy nên ở trường hợp này sóc bị mất tổng cộng \(18 + 15 = 33\).

• Ở cách này, sóc dừng lại ở trạm \(a_{3} = 15\) một giây cho nên tổng thời gian sóc đi là \(19\) giây nên bị rớt mất \(19\) quả và ở giây thứ \(4, 12\) sóc không ở trong trạm bảo vệ nên sóc bị trộm mất \(2 \times g = 10\) quả nữa. Vậy nên ở trường hợp này sóc bị mất tổng cộng \(19 + 10 = 29\).

Test 2

Input

18 10 100 3
0 8 15

Output

20

Note

• Nếu sóc đi thẳng một mạch thì sóc sẽ mất \(118\) quả vì đi hết \(18\) giây và ở giây thứ \(10\) sóc ở vị trí \(10\) không nằm trong trạm bảo vệ nào nên bị trộm mất \(100\) quả sầu riêng nữa.
• Sóc sẽ đi một cách khôn ngoan hơn bằng cách, dừng lại ở trạm \(a_{1} = 0\) trong \(2\)s và di chuyển một mạch về nhà. Nhờ đó ở giây thứ \(10\) sóc ở vị trí \(8\) và ở đó có trạm bảo vệ nên sóc không bị trộm mất quả sầu riêng nào nên tổng số quả sầu riêng bị mất là \(2 + 18 + 0 = 20\).

352 24 54 1
0

1108

20 5 4 4
0 5 10 15

20

65 20 100 4
0 14 25 33

172