Fast Forward

Gry has started to use the new Expify song streaming platform. Since, Gry does not want to spend money Expify forces him to listen to advertisements. An advertisement can be played only after some song (it cannot be played in the middle) and only if the time from the end of the previous advertisement is at least  seconds.

Gry has a circular playlist with  songs where the duration of the -th song is  seconds. He wants to minimize the number of advertisements, so, he wants to find out how many advertisements will be if he starts listening to his whole playlist from -th song, i.e., the circular playlist stops playing after  songs.

We suppose that there is an advertisement right before Gry starts listening. Neither this advertisement nor the one, after the playlist stops, count.

Input

itemize
  One line containing the number of songs in the playlist , and the refresh time between advertisements  (, )
  One line containing the  durations of the songs  ()
itemize

Output

Output the number of advertisements if Gry starts listening to the playlist from the -th song.
