Across the River

Chef Ciel would like to make a bridge on the river in order to purchase cooking ingredients more easily. The river is an infinitely long straight line with width W. To be more specific, the river is a set of the all points on 0 ≤ y ≤ W in xy-plane. There are N piles on the river, and M types of wooden disks are available. The location of the k-th pile is (Xk, Yk). The k-th type of wooden disks