P14948 Plants vs Zombies

> *There are zombies on your lawn...*

有 $n$ 名敌人将会按照顺序拜访你的草坪，第 $i$ 个敌人的血量是 $a_i$。草坪上有 $m$ 个陷阱，对每个 $1 \leq j \leq m$，都有一个计数器 $c_j$ 被设置在第 $j$ 个陷阱上。初始时，所有 $c_j$ 都是 $0$。 每名敌人都会从第 $1$ 个陷阱走到第 $2$ 个陷阱，一直走到第 $m$ 个陷阱。如果在走遍所有陷阱后它尚未死亡，它就会吃掉你的脑子。但与此同时，陷阱对敌人会造成伤害，一个敌人经过一个陷阱时，其血量会减少 $1$，对应陷阱的计数器会增加 $1$。一个敌人死亡，当且仅当它的生命值 **不高于** $0$。此时，它会被埋葬在对其造成对应伤害的陷阱下面，不再移动。 你可以花费一个金币，激活任意一个 $x \in [1, m]$ 的陷阱。激活后，当某名敌人经过陷阱 $x$ 时，$c_x$ 增加 $1$ 时恰好变为 $k$ 的倍数，那么此敌人的血量将会立刻变为 $0$。 你想要知道，最少花费多少个金币，就能防止自己的脑子被敌人吃掉。如果无论如何激活陷阱都不可能，输出 $\texttt{Zombies are on your lawn}$。

第一行，三个整数 $n$，$m$ 和 $k$（$1 \leq n \leq 100$，$1 \leq m \leq 100$，$\color{red}{1 \leq k \leq 3}$）。 第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq m + 1$）。

输出仅一行一个整数，表示最少花费的金币数目。如果无论如何激活陷阱都不可能，输出 $\texttt{Zombies are on your lawn}$。

对于第一组样例，只激活陷阱 $2$ 是最优的。所有计数器 $c_1, \ldots, c_m$ 的情况如下： - $[1, 0, 0, 0, 0]$； - $[2, 1, 1, 0, 0]$； - $[3, {\color{blue}2}, 1, 0, 0]$； - $[4, 3, 1, 0, 0]$； - $[5, {\color{blue}4}, 1, 0, 0]$。 对于第二组样例，其中一种最优方案是激活陷阱 $1$ 和 $4$。 对于第四组样例，无法保证你的脑子不被吃掉。