问题2527--THE END IS COMING!!!!!

2527: THE END IS COMING!!!!!

时间限制: 1 Sec  内存限制: 256 MB
提交: 62  解决: 28
[状态] [讨论版] [提交] [命题人:]
题目描述
    几年之前,大地的守护者耐萨里奥承受不住上古之神恩佐斯长时间的侵蚀,失去了理智,自称死亡之翼。 只有一种只存在于传说中的神器“巨龙之魂”才能帮助我们压制它的力量。你在一次冒险中意外发现了它, 所以,拯救世界的重担就扛在了你的肩上。
    使用巨龙之魂的第一步就是启动它。巨龙之魂由很多个机关构成,只有解开所有的机关我们才能使用它。
    在巨龙之魂的表面拥有一个坐标系统,两个机关之间的距离就是他们之间的曼哈顿距离。
    每个机关会在一个特定的时间开启,你必须在他开启的一瞬间开始解锁它(否则它就会崩坏),每个机关需 要一段时间来解锁。 
    你有 m 种元素,最多五种,不同的元素不能代替彼此。元素们由巨龙之魂中的一个洞送进来。 
    每个机关有自己的元素需求。比如第 i 个机关需要 cij 个 j 号元素来解锁。只有拥有了所有它需要的元素, 你才能开始解锁它。
    每个元素可以解锁无数个机关。也就是说,只要它在解锁完上一个机关时能够及时赶到下一个机关,它就 可以参与下一个机关的解锁。元素的移动速度是 1。
    有一些机关距离输送元素的洞太远了导致我们根本无法解锁它。红龙女王阿莱克斯塔萨赐予了我们生命的 力量,可以直接激发 k 个机关,如果我们还是有机关无法激活,那我们就无法阻止死亡之翼了。
    元素们都十分狂野并且难以控制,所以你需要用尽可能少的元素来激活巨龙之魂,最少多少个呢? 
输入
第一行三个数字,n(n<=100) ,m(m<=5) 和 k(k<=n/2),分别是机关的数量(包括输送元素的洞),元素 的种类,和可以直接激发的机关的数量。
第二行两个数字,输送元素的洞所在的坐标。 
接下来 n−1 行,每行信息如下所示: 
x y st ut c1 c2 ··· c 
x 和 y 代表这个机关的位置,st 是这个机关开启的时间,ut 是解锁这个机关需要的时间,c1-m 是每种元 素需要的数量。 
ci<=10 剩余的数字都小于 4e4。 
输出
一个数字,最少需要的元素数量。 
如果你无法激活巨龙之魂,你需要输出”THE END IS COMING!!!!!”(不含引号)

样例输入 Copy
4 2 2
0 0
1 0 1 1 3 3
1 1 3 1 2 2
0 1 2 10 1 1
样例输出 Copy
8
提示
首先我们有 3 个机关,有两个可以被直接激活。有两种元素可以被使用到。 
元素是从 (0,0) 被输送进来的。 
第 1 个机关在 (1,0) 位置,在第 1 分钟开启,需要 1 分钟来解锁,需要 3 个 1 号元素和 3 个 2 号元素来解 锁。 
第 2 个机关在 (1,1) 位置,在第 3 分钟开启,需要 1 分钟来解锁,需要 2 个 1 号元素和 2 个 2 号元素来解 锁。 
第 3 个机关在 (0,1) 位置,在第 2 分钟开启,需要 10 分钟来解锁,需要 1 个 1 号元素和 1 个 2 号元素来 解锁。 
用于解锁第一个机关的元素可以在第二个机关开启前赶过去,所以我们总共需要 6 个元素来解锁这两个机 关。 
第三个机关只能用新的元素来解锁,因为 12 机关的元素都赶不过去。。。 
所以我们总共需要 8 个元素来解锁所有的机关。

来源/分类