LJJ翻硬币

题目描述

LJJ在考试的时候由于不会选择题、填空题、解答题,于是,他通过抛硬币来决定写什么(填空、解答题里的每一个字符都通过抛硬币决定,强到不行,竟然满分,于是LJJ贡他唯一的硬币为神灵)。但是抛着抛着,LJJ发现翻硬币的游戏非常好玩,竟然比扫雷还好玩!于是,为了增加他的兴奋度,他就会进行一个游戏——从同学那里借来硬币摆成一行(毕竟他只有一个),并且兴(wu)奋(liao)地翻转其中的某些硬币。 但由于是同学借给他的,所以都是生锈的(为同学点赞),数据会给出每个硬币正面和反面的生锈度。 一共有n个硬币,LJJ每次会翻转k个硬币。每次翻转k个硬币,他的兴奋度会增加p,但同时兴奋度会减去每个被翻转硬币的生锈度之和。也就是说比如他准备翻2个正面向上的硬币,当前硬币的正面生锈度分别为2、3,那么他把这两枚硬币翻转到反面,兴奋度会增加p,同时兴奋度又减少了5。 注意,翻硬币也是会疲倦的,每一次翻转后p会减少1。所以你不能让LJJ无休止地把硬币翻下去。 一开始硬币的正反面情况为a1,a2,a3,.....,an。LJJ的目标是把这些硬币都翻到与开始时相反的一面。1表示正面,0表示反面。 于是PJY作为一个“关心学生”的好老师,他请你找出一个最好的硬币翻转方案,使得LJJ…

输入输出格式

输入格式


第一行:n,k,p三个正整数。详见描述。 第二行:n个数:a1,a2,a3,......,an。表示硬币的初始状态。 第三行到第(2+n)行:每行两个数x,y,表示第i个硬币正面和反面的生锈度。

输出格式


第一行:LJJ在达到目标的前提下最大的兴奋度。如果LJJ无法兴奋,即无解或兴奋度小于0,则输出0表示不可能。

输入输出样例

输入样例 #1

5  3  22
1 1 1 1 1
5 6
6 7
7 8
5 7
6 8

输出样例 #1

12

说明

对于50%的数据:0