A physics research lab is using a circular particle accelerator to detect dark matter. For convenience, scientists divided the circle into $N$ equal parts, marked them with points, and labeled them $1$ through $N$ in clockwise order. At time $t = 0$, a particle is at point $1$.

A particle with speed $u$ passes through exactly $u$ points clockwise per unit time. In other words, for a nonnegative integer $t_0$, if the particle is at point $i$ at time $t=t_0$ and its speed at that moment is $u$, then at time $t=t_0+1$ it will be at point $((i+u-1) \bmod N) + 1$.

The particle accelerator increases the particle's speed by $a$ per unit time. Specifically, the particle's speed is constant at $v$ for $0 \le t < 1$, constant at $v+a$ for $1 \le t < 2$, and in general, for any nonnegative integer $T$, the particle's speed is constant at $v + Ta$ for $T \le t < T + 1$.

Among the $N$ points of the accelerator, some points have observatories installed. There are $M$ observatories in total, and the $i$-th observatory is installed at point $p_i$. The $i$-th observatory can attempt to observe the particle only at positive integer times. An observation is successful only if the particle's speed is at least $s_i$ and its position is precisely the same as the observatory's position. An attempt for an observation costs $c_i$ and yields $g_i$ pieces of observation data. However, to avoid stressing the equipment, observations can be attempted at most $k_i$ times, and multiple observations cannot be attempted simultaneously at a single observatory. If multiple observatories are positioned at the same point, then two or more observatories may attempt observations simultaneously.

Find the earliest time to obtain at least $G$ data with a total cost of at most $B$.

Input

The first line contains three space-separated integers $N$, $a$, and $v$.

The second line contains three space-separated integers $M$, $B$, and $G$.

Each of the next $M$ lines contains five space-separated integers $p_i$, $s_i$, $c_i$, $g_i$, and $k_i$, describing an observatory.

Output

On the first line, print YES if there exists an integer $T$ such that at time $t=T$, it is possible to obtain at least $G$ pieces of observation data, and print NO otherwise.

If such $T$ exists, then on the second line, print the smallest such integer $T$.

Constraints

• $2 \le N \le 10^5$
• $0 \le a, v \le 10^5$
• $1 \le M, B \le 1000$
• $1 \le G \le 10^{12}$
• $1 \le p_i \le N$
• $0 \le s_i \le 10^9$
• $1 \le c_i \le B$
• $1 \le g_i \le G$
• $1 \le k_i \le B$

Scoring

Examples

Input 1

2 0 0
1 1 1
2 0 1 1 1

Output 1

NO

Input 2

2 0 1
1 1 1
2 0 1 1 1

Output 2

YES
1

Input 3

9 0 1
2 5 10
2 0 1 2 5
5 0 1 2 5

Output 3

YES
19