P2998 [USACO10NOV] Candy S

FJ 知道贝茜喜欢吃糖果。FJ 有 $N (1 \le N \le 40000)$ 颗糖果，他想在若干天内将这些糖果送给贝茜。每一天，FJ 会让贝茜从他提供的一个列表中选择她当天想吃多少糖果，该列表有 $Nopt(1 \le Nopt \le 50)$ 种不同的选项 $C_i (1 \le C_i \le N)$ 。她必须恰好拿走 $C_i$ 颗糖果。 农夫约翰给出了 $F(1 \le F \le 50)$ 个他喜欢的数字 $FN_i (1 \le FN_i \le N)$ 。每当一天结束时，如果剩余的糖果数量恰好等于这些数字之一，贝茜可以选择添加 $M（1 \le M \le 100)$ 颗糖果。如果添加糖果后又出现了另一个 FJ 喜欢的数字，贝茜可能会再次获得添加 $M$ 颗糖果的机会。在最好的情况下，贝茜可以获得无限多的糖果！ 当贝茜无法在列表中选择糖果数量（因为糖果不够）时，她就无法再获得更多糖果。 不幸的是，贝茜不知道该如何规划才能吃掉尽可能多的糖果，所以她需要你的帮助。 举例来说，考虑以下场景： * FJ 最初有 $10$ 颗糖果 * 贝茜每天可以选择吃掉 $3$ 或 $5$ 颗糖果 * 当剩余的糖果数量是 $2$ 或 $4$ 时，FJ 会添加 $1$ 颗糖果 贝茜可以使用以下选择来最大化她能吃掉的糖果数量： ```cpp 初始糖果数 吃掉糖果数 剩余糖果数 奖励糖果数 最终糖果数 第1天 10 3 7 0 7 第2天 7 3 4 1 5 第3天 5 3 2 1 3 第4天 3 3 0 0 0 ```

* 第 $1$ 行：四个由空格分隔的整数：$N,Nopt,F,M$ * 第 $2$ 行到第 $Nopt+1$ 行：第 $i+1$ 行包含一个整数：$C_i$ * 第 $Nopt+2$ 行到第 $Nopt+F+1$ 行：第 $i+Nopt+1$ 行包含一个整数：$FN_i$

* 第 $1$ 行：一个整数，表示贝茜能吃掉的最大糖果数量，如果贝茜能吃掉无限多的糖果，则输出 `-1`。