C1888 [2019nwu校赛]辛苦的志愿者

由于选手们实力过强，不断传来题目被 AC 的信息,在现场发气球的志愿者小姐姐们实在忙不过来了。初始所有志愿者小姐姐均在等待区,每当有一道题目被 AC,等待区就会产生一个气球。志愿者小姐姐发气球遵循以下规则：

1.如果此时等待区有志愿者，则志愿者出发将此气球发给对应的队伍，并在 $t$ 时间后返回等待区。

2.如果此时等待区没有志愿者，则等待某一个志愿者回到等待区再出发发这只气球。

3.当一个志愿者回到等待区时，等待区有待发放的气球，则这个志愿者会优先发放最早产生的气球。(如果有同时产生的气球，则优先发放对应队伍编号小的)

队员们在自己 AC 题目之后都翘首以待，盼着志愿者小姐姐出发向自己走来，而后在座位边亲手插上一只气球。俗话说的好，一时不见，思之如狂，便因而生恨。当某一队伍在 $a$ 时刻 AC 了某道题后，而小姐姐在 $b$ 时刻才出发发对应的气球，则这个队伍的怒气值会增加 $b-a$。如果某个队伍在任意时刻时怒气值大于或等于$d$，则会愤怒离场。

鸡尾酒只希望有队伍 AK 离场，而不希望有队伍愤怒离场。现在给你一场比赛的题目 AC 信息，请你帮鸡尾酒算算，他最少需要几个志愿者小姐姐来帮助他发气球才能保证没有队伍会愤怒离场且所有气球都被发放。

样例输入 1

3 2 2 3
1 1
3 1
2 2

样例输出 1

1