该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

无

Description

小苯很喜欢猫猫，因此他平时会接一些带猫猫出门遛弯的任务，也能得到一些报酬。

这天，小苯接到了 n 个带猫猫的任务，每个任务的内容都是将猫猫带到数轴某些指定的点上，并且小苯一次只能带一只猫猫。

具体的，在一条无限长的数轴（只考虑整数）上有 n 个猫猫，猫猫们的初始位置为 pos 数组，第 i 只猫猫的初始位置为 posi。小苯的任务是将猫猫们分别带到它们喜欢的点上，每只猫猫都有一个喜欢的数字，我们用数列 like 表示，第 i只猫猫喜欢的数字是 lilei。而一只猫猫喜欢的点就是，是所有他喜欢的数字的倍数的点。也就是说如果一只猫猫喜欢的数字是 y，那么只要满足 x%y=0，x 就是一个这只猫猫喜欢的点。

但是每只猫猫都有一点小脾气，小苯带着猫猫并不能想怎么走就怎么走，而应该顺从猫猫的心意。 具体的，每只猫猫都有一个要求，就是它的每一步必须是，要么往左走left的距离，要么往右走right的距离。形式化的：如果猫猫当前的位置是 pos，则他下一步必须要么是到pos - left，要么是到 pos+right。而不能是别的位置。

小苯如果把猫猫 i带到了它喜欢的点上，那么猫猫的主人会给小苯wi的报酬。

小苯每次带猫猫往左走一次就会消耗 p 点体力，每次带猫猫往右走一次就会消耗 q 点体力。小苯现在总共有 k 点体力，他想知道在他的体力被消耗到小于 0 之前，他最多能赚到多少报酬 ？

Format

Input

输入第一行包含四个正整数 n,p,q,k(1<=n,p,q,k<=3x$10^3$),分别表示，带猫猫任务的数量，往左走消耗的体力，往右走消耗的体力，小苯的总体力。 接下来输入n行，每行5个数字，分别代表题目中描述的 pos,like,w,left,right(1<=posi,likei,wi,righti<=3x$10^3$)。

Output

输出包含一行一个非负整数 max,表示你可以得到的最大报酬。

Samples

3 2 3 7
3 4 2 2 1
2 4 5 2 1
1 4 3 2 1

8

Limitation

1s, 1024KiB for each test case.