Euros Holmes has dominated over the Holmes Brothers.She is yet again plotting something diabolical.She has imprisoned John Watson and Mycroft Holmes. The only possibility to save them is to obey her orders.She gives Sherlock a map containing T towns.The towns are numbered as 0,1,....,T-1.She has hidden A[i] power gems in each of the town for Sherlock to collect.Sherlock gets tired as he searches and requires B[i] power gems to continue his travel.He can intake C power gems at a time.Consuming them,he can travel from town i to (i+1)%T.Initially Sherlock has no power gems with him.Sherlock wants to know from how many towns he could start his journey so that he can visit all the towns and return back to the town he started?

Constraints

2 ≤ T ≤ 10^5

1 ≤ C ≤ 10^18

0 ≤ A[i], B[i] ≤ 10^9

Input Format

The first line contains two integers (separated by a space): town number T and capacity C. The second line contains T space-separated integers: A[0], A[1], … , A[T - 1]. The third line contains T space-separated integers: B[0], B[1], … , B[T - 1].

Output Format

The number of towns which can be chosen as the departure town.