COCI '18 Contest 5 #2 Jarvis

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Ivan sent N drone warriors to the final battle against Tony Stark, also known as Iron Man. Each drone has a defined frequency, expressed as an integer number, on which it receives commands from Ivan during the fight. Jarvis, the artificial intelligence developed by Toni, has to determine which frequencies those are and thereby take control over as many drones as possible.

Jarvis knows the original factory values of the frequency for each drone, but the frequencies required for each drone, unfortunately, have been changed in the meantime.

Jarvis has only one attempt. He can choose an integer number X and increase each of the factory frequencies by X (X may be negative as well). After that, Jarvis will take over control of each drone whose modified factory frequencies and the one required by the specific drone is equal. Write a program that will determine how many drone warriors Jarvis can take control over.

Input

The first line contains the integer number N (1 \le N \le 100\,000), the number of drones from the task statement.

In the second line there are N integers A_i (-1\,000\,000 \le A_i \le 1\,000\,000) representing the factory frequency values of the drone warriors.

In the third line there are N integers B_i (-1\,000\,000 \le B_i \le 1\,000\,000) representing the required frequency values of the drone warriors.

Output

In the only line, print out the largest number of drone warriors Jarvis can take control over.

Scoring

In the test cases worth 40% of the points, all absolute values of the frequencies will be less than or equal to 10.

Sample Input 1

1
1
2

Sample Output 1

1

Sample Input 2

2
0 0
1 1

Sample Output 2

2

Sample Input 3

2
1 2
5 5

Sample Output 3

1

Explanation for Sample Output 3

If we choose X = 3, the factory frequencies will be 4 and 5, respectively (1 + 3 and 2 + 3), then Jarvis would take control only over the second drone warrior. If we choose X = 4, the factory frequencies will be 5 and 6 and then Jarvis would only take control over the first drone warrior. There is also no X such that Jarvis simultaneously takes control over both drone warriors.


Comments

There are no comments at the moment.