问题
Wolf Sothe 喜欢实现在线判断问题,他希望解决尽可能多的问题。但是,如果他每天不断地解决问题而不休息,那么一天能解决的问题数量就会一天天减少。
所以,有时 Wolf Sothe 会休息一天。在那一天,沃尔夫·索特不会解决任何问题,那么第二天和以后沃尔夫·索特就能解决问题。
Wolf Sothe一天能解决的问题数量如下:
- 如果那天是工作日,我们将 Wolf Sothe 持续解决问题的天数定义为 k (不包括那一天)。那么 Wolf Sothe 就可以解决 max(0, A − k \times B) 当天出现问题。
- 如果那天是休息日,那么当天就不会解决任何问题。
Wolf Sothe 想要解决问题 N 天。让 N 天按从第一天到第二天的顺序排列 N_{th} 天。假设沃尔夫·索特在第一天之前没有解决问题。
此外,我们提前知道有一些确定的休息日。
将给出所有已决定的休息日的列表。对于任何其他日期,您可以将其标记为休息日或工作日。请找出在此过程中可以解决的问题数量的最大值 N 天。
输入
输入将由以下格式的标准输入给出
N A B M t_1 t_2 : t_M
- 对于第一行,整数 N(1≦N≦1,000,000,000), A(1≦A≦1,000,000,000), B(1≦B≦1,000,000,000), M(0≦M≦100,000) 将用空格分隔。 M 表示已决定的休息天数。
- 从第二行开始有 M 附加行提供有关决定的休息日的信息。对于 i_{th} 行,一个整数 t_i(1≦t_i≦N) 代表 t_i 将给予决定的休息日。请注意,如果 i < j,那么 t_i<t_j
输出
请输出期间可以解决的问题数的最大值 N 天一线。
在输出末尾打印换行符。
输入示例 1
5 6 2 0
输出示例 1
20
假设沃尔夫·索特在第三天休息并解决剩余的问题 4 天。
- 第一天,Wolf Sothe 一直在解决问题 0 天。因此, max(0, 6 − 0 \times 2) = 6 问题。
- 第二天,Wolf Sothe 一直在为 1 天。因此, max(0,6 − 1 \times 2) = 4 问题。
- 第三天,沃尔夫·索特休息。因此, 0 问题。
- 第四天,Wolf Sothe 一直在为 0 天。因此, max(0, 6 − 0 \times 2) = 6 问题。
- 第五天,Wolf Sothe 一直在为 1 天。因此, max(0, 6 − 1 \times 2) = 4 问题。
总之, 6 + 4 + 0 + 6 + 4 = 20 将全部解决。
输入示例 2
6 4 3 1 3
输出示例 2
13
输入示例3
12 10 3 3 2 7 10
输出示例 3
71