Problem Description

You are playing ring toss with $N$ poles numbered from $1$ to $N$.

The ring toss is divided into three rounds: Round 1, Round 2, and Round 3. In each round, you must hit exactly $M$ different poles with rings. Note that all rings must be thrown, and the rings hit in each round remain on the poles even after the round ends.

When you hit a ring on pole $j$ in round $i$, you earn $(A_{j} \times (B_{j})^{i} \mod R_{i})$ points.

However, having too many rings on the same pole is not interesting. To maintain uniformity in the number of rings on each pole, an additional rule is added: After all rounds are finished, for each pole $j$ with one or more rings, if the number of rings on it is $i$, your score is reduced by $A_{j} \times (B_{j})^{i}$ points. Therefore, your final score may be negative.

You are trying to maximize your final score by appropriately deciding which poles to hit in each round.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $A_{1}$ $A_{2}$ $\ldots$ $A_{N}$ $B_{1}$ $B_{2}$ $\ldots$ $B_{N}$ $R_{1}$ $R_{2}$ $R_{3}$

Output Format

Output the maximum final score as an integer.

Sample Input and Output

Sample Input #1

2 1
3 2
3 3
100000 100000 100000

Sample Output #1

81

Sample Input #2

4 2
2 4 3 3
4 2 3 3
100000 100000 100000

Sample Output #2

210

Sample Input #3

20 19
3 2 3 4 3 3 2 3 2 2 3 3 4 3 2 4 4 3 3 4
2 3 4 2 4 3 3 2 4 2 4 3 3 2 3 4 4 4 2 2
3 4 5

Sample Output #3

-1417

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq M \leq N \leq 500$
• $2 \leq A_{i}, B_{i} \leq 1000$
• $2 \leq R_{1}, R_{2}, R_{3} \leq 10^{5}$

Sample Explanation 1

• In each of Round 1, 2, and 3, hitting a ring on pole 1 earns you 9, 27, and 81 points, respectively.
• In each of Round 1, 2, and 3, hitting a ring on pole 2 earns you 6, 18, and 54 points, respectively.
• After all rounds, if there are 1, 2, or 3 rings on pole 1, the points deducted are 9, 27, and 81, respectively.
• After all rounds, if there are 1, 2, or 3 rings on pole 2, the points deducted are 6, 18, and 54, respectively.
  The optimal strategy is to hit the ring on pole 2 in Round 1 and on pole 1 in Round 2 and 3.

见题面 Input 部分

见题面 Output 部分