20329번 - Aquarium 다국어

문제

The aquarium at which you work is hoping to expand its meagre selection of aquatic life, but lacks the funds to do so. You have been tasked to help promote the aquarium by taking photos of the two exhibits. Taking the first photo went swimmingly, because the catfish were very cooperative. For the piranhas, you have an arrangement of piranhas in mind that will look great on the photo. However, the only way to get the piranhas to move is by recklessly sticking your finger into the water to lure the piranhas. Your goal is to move the piranhas to the desired positions as quickly as possible without losing your finger in the process.

The piranha exhibit can be divided into positions 1,ドル\ldots,n$ from left to right. The exhibit contains $k$ piranhas and every position is occupied by at most one piranha. You can stick your finger into any unoccupied position. This will lure the nearest piranha to the left of your finger and the nearest piranha to the right of your finger. These piranhas will swim towards your finger, moving forward one position per second. All other piranhas simply stay in place. A piranha will bite your finger if it reaches the same position, so you must pull your finger away before this happens. Pulling your finger away and sticking it into a different position does not take any time.

For example, suppose there are piranhas at positions 2ドル,ドル 7ドル$ and 9ドル$. If you stick your finger into the water at position 4ドル,ドル the piranhas will be at positions 3ドル,ドル 6ドル$ and 9ドル$ after one second. You now have to pull your finger away to prevent the piranha at position 3ドル$ from biting your finger one second later. If you now stick your finger into the water at position 1ドル,ドル only the piranha at position 3ドル$ will move and will end up at position 2 after one second.

입력

• One line containing two integers $n$ (1ドル\leq n\leq1000$), the number of positions, and $k$ (1ドル\leq k\leq n$), the number of piranhas.
• One line containing $k$ integers 1ドル\leq p_1<\ldots<p_k\leq n,ドル the current positions of the piranhas.
• One line containing $k$ integers 1ドル\leq d_1<\ldots<d_k\leq n,ドル the desired positions of the piranhas.

출력

Output the minimum number of seconds needed to get all of the piranhas at the desired positions. If it is impossible to do so, output "impossible".

제한

힌트