기념품 구매 계획 (Gifts) timer 15초 memory 128MB

호주로 여행을 간 태영이는 다양한 장소에서 관광을 즐기고, 마침내 귀국하는 날이 왔다. 현재, 태영이는 돌아가는 비행기가 출발하는 국제공항의 동네에 있다. 그 마을에는 동서남북으로 구역정리가 되어있으며, 각 구역에는 길, 기념품, 주택, 국제공항이 있다. 태영이는 가장 북서쪽의 구역에서 출발하여 가장 남동쪽에 있는 구역의 국제공항으로 가려고 한다.

태영이는 지금부터 가장 가까운 구역을 이동할 수 있으며, 주택구역은 들어가지 못한다. 또 비행기출발 시간을 맞추기 위해서 지금 있는 구역부터 동쪽과 남쪽으로 밖에 이동 하지 못한다. 단, 시간이 어느 정도 여유가 있기 때문에, K번 동안 지금 있는 구역에서 북, 서쪽으로 이동이 가능하다.

태영이는 기념품 가게가 있는 구역으로 들어가면, 한국에 있는 친구 관영이를 위해서 기념품을 사려고 한다.  태영이는 기념품 가게를 꼼꼼히 미리 조사해 두었으며, 기념품 가게에 가면 몇 개의 기념품을 살 수 있는지 알고 있다. 태영이가 최대 몇 개의 기념품을 살 수 있는지에 대한 프로그램을 작성 하여라.

하지만, 기념품을 구매하는 시간은 무시하여도 좋으며, 같은 기념품을 2번 이상 찾았을 때는 처음 것만 계산한다.

입력 예 1을 보면 예제 1번에서, 먼저 태영이가 3번 남쪽으로 이동하여 구역(4,1)의 기념품가게에서 물건을 구매한 뒤에, 남쪽으로 1번, 동쪽으로 3번 더 가서, 거기서 북쪽으로 2번 뒤에 있는 구역(3,4)의 기념품 가게에서 물건을 구매하였다. 마지막으로 남쪽으로 2번 가서 국제공항에 도착하면 총 11개의 기념품을 구매할 수 있다.