No.2244 Integer Complete
Problem Statement
Shobon-kun is currently absorbed in a card game called "Integer Complete". In this card game, you prepare $2$ decks, deck $A$ and deck $B$, and put some cards into each deck.
Shobon-kun has put $N$ cards $A_1, A_2, \cdots, A_N$ into deck $A$ and $M$ cards $B_1, B_2, \cdots, B_M$ into deck $B$. In "Integer Complete", you battle by placing integers on the field. An integer can be placed on the field by performing the following [Action].
[Action] Choose a card $A_i ~ (1 \le i \le N)$ from deck $A$ and $1$ integer $x$ satisfying $A_i^2 \le x \lt (A_i+1)^2$. Next, choose a card $B_j ~ (1 \le j \le M)$ from deck $B$ and $1$ integer $y$ satisfying $B_j^2 \le y \lt (B_j+1)^2$. Then, place the product $xy$ of $x$ and $y$ on the field.
Find the smallest positive integer that Shobon-kun cannot place on the field.
Constraints
- All inputs are integers
- $1 \le N, M \le 3 \times 10^4$
- $1 \le A_1 < A_2 < \cdots < A_N \le 3 \times 10^4$
- $1 \le B_1 < B_2 < \cdots < B_M \le 3 \times 10^4$
Input
$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$
Output
Output the smallest positive integer that Shobon-kun cannot place on the field.
It can be shown that an answer exists under the constraints.
Sample
Sample 1
Input
2 1 1 2 1
Output
11
The integers that can be chosen from deck $A$ are $1, 2, 3, 4, 5, 6, 7, 8$, and the integers that can be chosen from deck $B$ are $1, 2, 3$. For example, for the positive integer $10$, you can choose $5$ from deck $A$ and $2$ from deck $B$ to place their product, $10$, on the field.
All positive integers less than or equal to $10$ can be placed on the field. However, no matter how you choose integers from deck $A$ and deck $B$, you cannot place the positive integer $11$ on the field. Therefore, output $11$.
Sample 2
Input
1 1 1 2
Output
1
The integers that can be chosen from deck $A$ are $1, 2, 3$, and the integers that can be chosen from deck $B$ are $4, 5, 6, 7, 8$. No matter how you choose integers from deck $A$ and deck $B$, you cannot place $1$ on the field, so output $1$.
Sample 3
Input
2 3 1 2 1 3 4
Output
25
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
Nachia