410079: GYM103938 G Larry Longsleeves

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Larry Longsleevestime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Larry Longsleeves is reknown for having the finest collection of long shirts and long pants in the world. After winning the International Longsleeve Showdown five years in a row, he's confident that he's uncovered the secrets of stylish outfits. To maximize on his discovery, he's decided to start his own clothing company, with the help of Convergent!

In his pitch, Larry plans to reveal that each outfit, consisting of just one shirt and one pair of pants, can be reduced to a style score $$$s$$$! Even better, there's a formula to compute it, based solely on $$$a$$$, the length of the shirt sleeves, and $$$b$$$, the length of the pant sleeves: $$$s = |a^2-b^2|$$$. But while a higher value of $$$s$$$ is preferred, an outfit can only truly be stylish if $$$s$$$ is prime. This insight, as Larry claims, will allow his brand to suggest the best outfit combinations for the customers and beat out his competition.

However, the members of Convergent aren't convinced. After all, while Larry has won the International Longsleeve Showdown many times, he also has the most extensive wardrobe in the world — perhaps he just got lucky when selecting the winning outfits?

In any case, it is your job to help out Larry. He needs a stylish outfit, and fast. As his second in command, personal butler, and best friend, can you look through his wardrobe and find Larry Longsleeves an outfit to win Convergent over?

Input

The first line of input contains two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^4$$$), representing the number of shirts and pants Larry has, respectively.

The second line contains $$$n$$$ integers, $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$), representing the sleeve length of each shirt that Larry has.

The third line contains $$$m$$$ integers, $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^6$$$), representing the sleeve length of each pair of pants that Larry has.

Output

Output the highest style score achievable of any of Larry's stylish outfits, or $$$-1$$$ if no combination of Larry's shirts and pants yields a stylish outfit.

ExamplesInput
2 3
2 4
1 3 5
Output
7
Input
1 3
2
4 6 8
Output
-1

加入题单

算法标签: