在一个鲜为人知但非常美丽的国家沃特兰,生活着一只可爱的鲨鱼瓦莱丽。像所有鲨鱼一样,她有几排牙齿,以鲫鱼为食。瓦莱丽的显着特征之一是,在吃一只鲫鱼时,她只使用一排牙齿,其余牙齿都在“放松”。
很长一段时间以来,我们的女主角一直在海上寻找鲫鱼,但一场巨大的不幸发生了。她的牙齿开始疼痛,她不得不去看当地的牙医龙虾阿肖特。作为一名专业人士,阿肖特很快就缓解了瓦莱丽的牙痛。此外,他还设法确定了瓦莱丽患龋齿的原因(后来他被昵称为“Cap”)。
原来瓦莱丽吃了太多鲫鱼。为了帮助瓦莱丽避免再次出现牙痛,阿肖特发现了瓦莱丽每颗牙齿的残余活力。一颗牙齿的剩余生存能力等于瓦莱丽用这颗牙齿可以吃掉的鲫鱼数量。瓦莱丽每吃掉一条鲫鱼,用于它的所有牙齿的生存能力就会减少一颗。当至少一颗牙齿的活力变为负值时,鲨鱼将不得不再次去看牙医。
瓦莱丽不高兴地回到家,那里有一些鲫鱼在等着她。当然,鲨鱼无法拒绝她最喜欢的食物,但她不想再去看牙医。这就是为什么她决定从这部分中吃掉最大数量的鲫鱼,但这样没有牙齿的生存能力就会变成负值。
由于瓦莱丽不擅长数学,她要求你帮她算出她晚餐可以吃的鲫鱼总量。
我们应该提醒您,在吃一条鲫鱼时,瓦莱丽只使用一排牙齿,并且该排中每颗牙齿的活力都会减少一颗。
输入
第一行包含三个整数 n、m、k (1 ≤ m ≤ n ≤ 1000, 0 ≤ k ≤ 106) — Valerie 晚餐中的牙齿总数、牙齿排数和鲫鱼数。然后是 n 行,每行包含两个整数:r (1 ≤ r ≤ m) — 行的索引,其中属于相应的牙齿,c (0 ≤ c ≤ 106) — 其剩余活力。
保证每个齿排的齿数为正数。
输出
第一行输出 Valerie 晚餐可以吃的鲫鱼的最大数量。
示例
输入 #1
4 3 18 2 3 1 2 3 6 2 3
输出 #1
11
输入 #2
2 2 13 1 13 2 12
输出 #2
13