时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
在甜蜜的梦乡中，mzt变成了小人国的一名粉刷匠。
一天，国王命令mzt去粉刷一条走廊的道路，这个走廊的道路由
块地板组成。从左到右每块地板标号
。
勤劳的mzt立刻带了
种不同的颜料前去干活。每种颜料标号为
。因为地板材质不同，有木地板、瓷地板、草地等等，所以不同块地板对不同颜料的吸收程度是不同的。这意味着，mzt对
号地板涂以
号颜色，需要花费他
点体力。
但是，国王的要求怎么会这么简单呢？国王有他自己的癖好，他会提前告诉mzt，哪几块地板必须涂成什么颜色，比如标号为
的地板必须涂成标号为
的颜色。
此外，国王还有他自己的幸运数字
，这意味着国王要求地板的颜色必须被分成块，连续相同颜色的地板被认为是一块。例如地板从左到右颜色分别为
。它可以被分成
块：
。
mzt希望你来帮他解决，最少需要花费的体力点数，去满足国王的任务要求。
一天，国王命令mzt去粉刷一条走廊的道路，这个走廊的道路由
勤劳的mzt立刻带了
但是，国王的要求怎么会这么简单呢？国王有他自己的癖好，他会提前告诉mzt，哪几块地板必须涂成什么颜色，比如标号为
此外，国王还有他自己的幸运数字
mzt希望你来帮他解决，最少需要花费的体力点数，去满足国王的任务要求。
输入描述:
输入第一行给出个整数
，地板的数量，颜料种类，国王的幸运数字和国王的怪癖数。
下面行给出国王对特定块地板的要求，每行两个整数
，即
号地板必须被涂成
号颜色，但是国王有点心神不定，这意味着部分标号地板可能会遇见不同要求，以最后一次对此地板的要求为准。
接下来的
输出描述:
输出一个整数，最少需要花费的体力点数。如果不能满足国王的要求则输出。