B'There are many freight trains departing from Kirnes planet every day. One day on that planet consists of h hours, and each hour consists of m minutes, where m is an even number. Currently, there are n freight trains, and they depart every day at the same time: i -th train departs at h_i hours and m_i minutes. The government decided to add passenger trams as well: they plan to add a regular tram service with half-hour intervals. It means that the first tram of the day must depart at 0 hours and t minutes, where 0 <= t < {m over 2} , the second tram departs m over 2 minutes after the first one and so on. This schedule allows exactly two passenger trams per hour, which is a great improvement. To allow passengers to board the tram safely, the tram must arrive k minutes before. During the time when passengers are boarding the tram, no freight train can depart from the planet. However, freight trains are allowed to depart at the very moment when the boarding starts, as well as at the moment when the passenger tram departs. Note that, if the first passenger tram departs at 0 hours and t minutes, where t < k , then the freight trains can not depart during the last k - t minutes of the day. Unfortunately, it might not be possible to satisfy the requirements of the government without canceling some of the freight trains. Please help the government find the optimal value of t to minimize the number of canceled freight trains in case all passenger trams depart according to schedule. The first line of input contains four integers n , h , m , k ( 1 <= n <= 100 ,000 , 1 <= h <= 10^9 , 2 <= m <= 10^9 , m is even, 1 <= k <= {m over 2} ) -- the number of freight trains per day, the number of hours and minutes on the planet, and the boarding time for each passenger tram. n lines follow, each contains two integers'...