You are playing a popular browser game where you collect fleet girls to fight against enemies, the Abyssals. However, you prefer to spend your time playing ExpedColle, a "sub-game" where all you do is run expeditions all day, getting the most resources out of your time. There are many different classifications of ships in the game, but the only one relevant to you is the Mutsuki-class destroyer. The Mutsuki-class is famous for its low resource costs while on expedition.

An expedition is an action you can perform that starts a timer. When the timer completes, you gain a certain amount of resources (fuel, ammo, steel, or bauxite) and/or other items. And after completing an expedition, you must resupply your ships, which uses up some resources (typically fuel and ammo). In the game, there are many different expeditions. Expeditions can be organized by the world they take place in. In total, there are $N$ worlds in the game. Each world can be described with nine parameters, $E$, $C_1$, $V_1$, $CA$, $CB$, $CM$, $VA$, $VB$, and $VM$. $E$ is the number of expeditions available to you in that world. To simplify our model a little bit, we can say that the resource cost of an expedition is $C_i$ and the revenue from completing it is $V_i$. For each world, the first expedition has cost $C_1$ and revenue $V_1$. Every subsequent expedition $i$ has cost $C_i=(C_{i-1}\times CA+CB)modCM$ and value $V_i=(V_{i-1}\times VA+VB)modVM$.

You want to seem like an elite player, so you refuse to do any expedition more than once. You have $R$ resources to spend in total on performing expeditions. What is the maximum revenue you can make? You do not necessarily have to spend all of your resources. Note that completing expeditions does not give you more usable resources to initiate other expeditions.

Input Specification

The first line of input will have $N$ and $R$.
The next $N$ lines of input will each have $E$, $C_1$, $V_1$, $CA$, $CB$, $CM$, $VA$, $VB$, $VM$ (one line per world).

Constraints

For all subtasks:

$1\le N\le 2000$

$1\le R\le 2000$

$0\le C_1,CA,CB<CM\le {10}^9$

$0\le V_1,VA,VB<VM\le {10}^9$

Subtask 1 [40%]

The sum of $E$ over all worlds does not exceed ${10}^5$.

Subtask 2 [60%]

The sum of $E$ over all worlds does not exceed ${10}^7$.

Output Specification

Output the maximum revenue within the given resource budget.

Sample Input

2 25
1 10 10 99 99 100 99 99 100
5 3 2 4 7 11 6 7 13

Sample Output

23

Explanation of Output for Sample Input

The expeditions in $(cost,value)$ pairs are:

• World 1: $(10,10)$
• World 2: $(3,2)$, $(8,6)$, $(6,4)$, $(9,5)$, $(10,11)$

Do the first expedition from world 1, the first expedition from world 2, and the last expedition from world 2 for a total cost of $10+3+10=23$ and value of $10+2+11=23$.