Problem C
The Duckamyds
Languages
en
sv
Kalle has just received a large box of colorful rubber ducks as a gift. After counting them carefully, he knows exactly how many ducks he has of each color. Now, he wants to build the world’s largest duck pyramid!
To build the pyramid, Kalle has borrowed a special pyramid construction stand whose height allows him to build a pyramid with up to $M$ layers of ducks. A duck pyramid is built in layers, where the bottom layer is layer 1, the next is layer 2, and so on. To make the pyramid look nice, Kalle has decided that each layer should consist of ducks of the same color. He has also decided which color each layer should have.
If the pyramid has height $H$, then layer $i$ must contain exactly $(H-i+1)^2$ ducks. For example, in a pyramid with height 3:
-
Layer 1 (bottom) needs $3^2 = 9$ ducks.
-
Layer 2 (middle) needs $2^2 = 4$ ducks.
-
Layer 3 (top) needs $1^2 = 1$ duck.
![\includegraphics[width=0.5\textwidth ]{ankamyd.png}](/problems/ankamyderna/file/statement/en/img-0001.png)
Help Kalle calculate how tall the pyramid can be! Note that the height $H$ cannot exceed $M$.
Input
On the first line, there are two integers $N$ and $M$ ($1 \le N, M \le 10^5$), the number of different colors and the number of layers in the pyramid.
On the second line, there are $N$ integers $a_1, a_2, ..., a_N$ ($0 \le a_j \le 10^{18}$), where $a_j$ indicates the number of ducks of color $j$.
On the third line, there are $M$ integers $c_1, c_2, ..., c_M$ ($1 \le c_i \le N$), where $c_i$ indicates which color should be used in layer $i$.
Note that even though Kalle has decided which colors all layers should have, he may build a pyramid that does not use all $M$ layers.
Output
Print an integer: the maximum height $H$ the pyramid can have.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
Group |
Points |
Constraints |
$1$ |
$11$ |
$N = 1$ |
$2$ |
$19$ |
$c_i = i$, for all $1 \leq i \leq M$. |
$3$ |
$17$ |
$\sum a_k \le 10^5$ |
$4$ |
$19$ |
$N, M \le 2000$ |
$5$ |
$34$ |
No additional constraints. |
Explanation of Samples
In the first example, Kalle only has ducks of one color, and he has 17 of them. The pyramid stand allows up to 5 layers. To build a pyramid of height 3, the following ducks are needed:
-
9 ducks in layer 1
-
4 ducks in layer 2
-
1 duck in layer 3
A total of 14 ducks are used. It is not possible to build a pyramid with height 4, because that would require $4^2 + 3^2 + 2^2 + 1^2 = 30$ ducks, which is more than the 17 ducks available.
In the second example, Kalle has:
-
2 ducks of color 1
-
19 ducks of color 2
-
12 ducks of color 3
The color order in the layers is: 2, 3, 2, 1, 2. A pyramid of height 3 can be built by using:
-
9 ducks of color 2 in layer 1
-
4 ducks of color 3 in layer 2
-
1 duck of color 2 in layer 3
This uses 10 ducks of color 2 and 4 ducks of color 3, which is within the available limits. A taller pyramid is not possible with the given restrictions.
Sample Input 1 | Sample Output 1 |
---|---|
1 5 17 1 1 1 1 1 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
3 5 2 19 12 2 3 2 1 2 |
3 |
Sample Input 3 | Sample Output 3 |
---|---|
2 3 4 2 1 2 1 |
2 |