#40 「 天天寄快递 」

统计

天天暑假时帮别人寄送快递,经历了一个暑假,天天积累了不少数据,想对快递公司进行一下评分,得到快递公司的质量水平。

总共有$n$家快递公司,编号为$1 .. n$。现在天天有$m$ 天的寄送快递数据,其中第$i$天使用第$e_i$家快递公司,快递在路上花了$t_i$ 天时间。一开始每个快递公司的评分都为$0$,对于一家快递公司,如果一个包裹花了$t_i$天寄到,那么对这家快递公司的评分贡献为$2 - t_i$,(如果花的时间超过两天得分就会变成负的啦)。

然而事情没有这么简单,如果某一天的数据丢掉了,天天为了公平起见就忽略掉这天的数据。于是快递公司联盟决定雇佣一个小偷,小偷可以偷走最多$s$天的数据,使得每个公司的信用得分至少增加$k$,且所有快递公司的信用总和尽量大。

若如果被偷以后,无法让每个公司的信用得分都至少增加$k$,输出$-23333333$,否则请你输出被偷后,所有快递公司的信用得分的和最多增加多少。

输入格式

第一行四个整数$n, m, s, k$,其中$1 \le n, m \le 100,000, 0 \le s \le m, 0 \le k \le 10^9$。

接下来$m$行,每行两个整数。接下来的第$i$行为$e_i, t_i$,其中$1 \le e_i \le n, 0 \le t_i \le 10^9$。

输出格式

一个整数,为题目要求的答案。

样例数据

input

2 5 4 22
1 1
1 40
2 25
2 30
2 0

output

89

样例解释

小偷可以偷$4$天的数据,但是小偷实际上只偷了第$2,3,4$天的数据,$1$号公司获得了$38$分的提升,$2$号公司获得了$23+28$分的提升,都满足了最小提升$22$分的要求。

数据规模与约定

$1 \le n, m \le 200,000$。

时间限制:1s

空间限制:512MB

Author: Chenyao2333