Background

She is Mine.

Problem Description

In late autumn, leaves are falling everywhere, and Ciky is very happy.

$\texttt{Augen}$ took the kids to the woods and picked up many golden leaves.

All the leaves they picked are regular polygons. Now $\texttt{Augen}$ plans to turn them into specimens, bind them into an album, and give it to Ciky.

To make one specimen, you need to color along the edge of a leaf, and the edge colors of different leaves must be different. Also, each specimen has a corresponding beauty value.

When binding the specimens into an album, the following conditions must be satisfied:

• The perimeter of the $i$-th leaf must not be greater than the perimeter of the $(i+1)$-th leaf.
• The beauty value of the $i$-th leaf must not be greater than the beauty value of the $(i+1)$-th leaf.

$\texttt{Augen}$ has $n$ pens of different colors, and the $i$-th pen can draw a total length of $a_i$.

There are $m$ leaves. The $i$-th leaf is a regular $k_i$-gon, each side has length $b_i$, and its beauty value is $c_i$.

More simply, only when $k_i * b_i \leq a_j$ can the $j$-th pen be used to draw the $i$-th leaf.

In particular, after a leaf is finished using the $i$-th pen, its perimeter becomes $a_i$. Each pen can draw at most one leaf.

$\texttt{Augen}$ hopes either to give away more specimens, or to maximize the total beauty value of the specimens made.

Note: The two questions are independent.

Input Format

The first line contains two integers, $n, m$.

The second line contains $n$ integers. The $i$-th integer denotes $a_i$.

The third line contains $m$ integers. The $i$-th integer denotes $b_i$.

The fourth line contains $m$ integers. The $i$-th integer denotes $c_i$.

The fifth line contains $m$ integers. The $i$-th integer denotes $k_i$.

Output Format

There are two lines.

The first line contains one integer, the maximum possible number of specimens in the album.

The second line contains one integer, the maximum possible total beauty value of the specimens made.

Note: The second question does not require putting the specimens into the album.

5 3
9 7 2 5 6
1 2 1
2 6 8
3 3 4

3
16

Hint

Sample Explanation

For the first question, use the $4$-th pen to draw the $1$-st leaf, the $5$-th pen to draw the $2$-nd leaf, and the $1$-st pen to draw the $3$-rd leaf. The resulting perimeters are $5, 6, 9$, so you can draw $3$ leaves.

For the second question, you can use the same method. The total beauty value is $2 + 6 + 8 = 16$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \leq n, m \leq 10^6$, $3 \leq k_i \leq 10^6$, $1 \leq a_i \leq 10^9$, $1 \leq b_i, c_i \leq 10^6$.

Translated by ChatGPT 5