Arcade
Time limit1sMemory limit1024 MB
Each hand moves one button per second between presses; find the minimum number of hands that can cover all M presses.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Intervals, Implementation
- Solved
- No attempts yet
Problem
Emily the alien octopus is playing an arcade game. The machine has N buttons, numbered 1 to N from left to right. The game consists of pressing M buttons, one per second. At time Ti seconds after the game starts, button Ai must be pressed. It is possible that Ti = Tj and Ai = Aj even when i ≠ j.
Each of Emily's hands can start at any position when the game begins, and moving a hand from a button to an adjacent button takes exactly one second. Emily's hands can move simultaneously, and pressing a button takes no time. Since alien octopuses have infinitely many hands, Emily can always earn the maximum score by completing all M presses. But Emily is lazy, so she does not want to use all her hands. Let S be the minimum number of hands needed to earn the maximum score.
Given the exact sequence of button presses Emily must perform, find the minimum number of hands she needs in order to earn the maximum score. Find the value of S and give it to Emily.
Input
Your program must read from standard input.
The first line contains two integers N and M.
The second line contains M integers, where the i-th integer is Ti.
The third line contains M integers, where the i-th integer is Ai.
Output
Your program must print to standard output.
The output must be a single integer on one line: the minimum number of hands Emily needs in order to earn the maximum score.
Constraints
- 1 ≤ N ≤ 10^9
- 1 ≤ M ≤ 5 × 10^5
- 1 ≤ Ai ≤ N
- 1 ≤ Ti ≤ 10^9