시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

Emily the alien octopus is playing an arcade game. The game machine consists of N buttons, numbered 1 to N from left to right. The game involves pressing a series of M buttons, one per second. At Ti seconds from the start of the game, button Ai must be pressed. Note that it is possible for Ti = Tj, Ai = Aj even if i ≠ j.

Each of Emily’s hands can start at any position at the start of the game, and it takes exactly one second for Emily to move a hand from a button to an adjacent button. Emily’s hands can move simultaneously, and it takes no time to press a button. As alien octopuses have an infinite number of hands, it is always possible to obtain the maximum score on the game by completing all M button presses. However, as Emily is lazy, she does not want to use all her hands. Let the minimum number of hands required to obtain the maximum score be S.

Given the exact series of button presses Emily has to accomplish, help her find out the minimum number of hands she needs to use to obtain the maximum score for the game. Help find and provide Emily the value of S.

입력

Your program must read from standard input.

The first line contains two integers N and M.

The second line contains M integers, where the ith integer represents Ti.

The third line contains M integers, where the ith integer represents Ai.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the minimum number of hands Emily needs to use to obtain the maximum score for the game.

제한

  • 1 ≤ N ≤ 109
  • 1 ≤ M ≤ 5 × 105
  • 1 ≤ Ai ≤ N
  • 1 ≤ Ti ≤ 109

예제 입력 1

6 4
1 2 3 4
3 1 2 6

예제 출력 1

2

At the start of the game, Emily’s hands will be in the following positions, with her right hand pressing button 3:

In the next second, Emily will move her right hand one button to the right, and press button 1 with her left hand.

After which, she will move both hands one button to the right simultaneously, and press button 2.

In the final second, she will move her right hand one step to the right and press button 6

Therefore, Emily would require two hands to complete the game. S would thus have the value of 2 and the program would output 2.