P6917 [ICPC 2016 WF] Balanced Diet

每天，Danny 都会从糖果店买一颗糖并吃掉它。糖果店中有 $m$ 种糖，编号为 $1 \dots m$ 。 Danny 知道均衡饮食很重要，他正在尝试在购买糖果时有一个均衡的饮食。因此他给每种糖 $i$ 分配了一个目标分数 $f_i (0 \le f_i \le 1, f_i$ 为一个实数 $) $, 。他希望他所吃的所有糖中，第 $i$ 种糖的数量占比大概为 $f_i$ 。 准确的说， 令 $s_ i$ 表示 Danny 已经吃掉的第 $i$ 种糖的数量, $n = \sum _{i=1}^ m s_ i$, 我们认为一种吃糖的方法是均衡的仅当对于所有的 $i$，满足： $$n f_ i - 1 < s_ i < n f_ i + 1$$ Danny 已经购买并吃掉了一些糖，并且他保证每个前缀的饮食都是均衡的。他想知道在保证每个前缀均衡饮食的条件下，他最多还能吃多少颗糖。 给定目标分数 $f_i$ 和他已经吃过的糖果序列，请你确定在保证每个前缀均衡饮食的条件下，Danny 最多还能购买并吃掉多少颗糖果。

输入包含三行。第一行包括两个整数 m $1 \le m \le 10^5$ 表示糖果的种类, $k(0 \le k \le 10^5)$ 表示 Danny 已经吃掉的糖果数量。 第二行包括 $m$ 个正整数 $a_1 \dots a_m$, 有 $ \displaystyle f_ i = \frac{a_ i}{\sum _{j = 1}^ m a_ j}$, 保证 $\sum_{i=1}^m a_i \le 10^5$ 。 第三行包括 $k$ 个正整数 $b_1 \dots b_k (1 \le b_i \le m)$, 表示 Danny 在第 $i$ 天购买并吃掉的糖的种类。保证序列的每个前缀（包括整个序列）是饮食均衡的。

输出在保证每个前缀饮食均衡的条件下，Danny 最多还能购买并吃掉多少颗糖。 如果糖果的数量没有上限（即 Danny 能一直买下去），输出 `forever`。

Time limit: 2000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2016