Церемония закрытия Squanch Code Cup проводится в большом зале на n × m человек. Сам зал состоит из n рядов, в каждом из которых находится m стульев. Каждый стул имеет две координаты: (x, y) (1 ≤ x ≤ n, 1 ≤ y ≤ m).
На вход в зал столпилось две очереди: k человек находится в точке с координатами (0, 0), и n·m - k человек в точке с координатами (0, m + 1). У каждого человека должен быть билет на определённое место. Если у человека p с начальными координатами (x, y) билет на место (xp, yp), ему нужно будет пройти |x - xp| + |y - yp|.
Про каждого человека известна его выносливость, а именно какое максимальное расстояние он может пройти. Ваша задача узнать, можно ли распределить все билеты, чтобы каждый человек смог дойти до своего места.