시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 16 7 7 63.636%

문제

김상근과 김정인이 그녀의 마음을 얻기 위해 경쟁을 벌이고 있따. 그들은 다음과 같은 방법으로 승자를 결정하기로 했다.

무한한 크기의 2차원 평면에 어떤 지점에서 그녀가 걷기 시작한다. 그리고 그녀는 상, 하, 좌, 우 4방향으로 걸어갈 수 있는데 한번 걸어갈때마다 마음이 바뀐다. 즉, 상근이를 좋아하고 있었다면 정인이를 좋아하게 되고 정인이를 좋아하고 있었다면 상근이를 좋아하게 된다. 시작점에서는 그녀가 상근이를 좋아한다고 한다. 또한 2차원 좌표판 중에는 장애물이 있는 곳이 있어서 그런 곳은 지나가지 못한다고 하자. 이때 그녀는 그 시작점에서 (0, 0)까지 장애물을 피하여 최단거리로 걸어온다고 가정한다.

그녀가 무한한 체력을 가진 것은 아니므로 그녀가 걷는 걸음수를 S걸음 이하로 제한할 때 2차원 좌표 중 최종적으로 그녀가 (0, 0)에 왔을때 상근이를 좋아하게 될 시작점의 개수와 정인이를 좋아하게 될 시작점의 개수를 구하라.

입력

첫 줄에는 장애물의 개수 B와 걸음수 S가 주어진다. (1<=B<=10000, 1<=S<=10000000) 그리고 다음 B줄에는 장애물의 좌표가 주어진다. 장애물의 x, y값의 절대값은 1000보다 작다고 하자.

출력

상근이를 좋아하게 될 시작점의 개수와 정인이를 좋아하게 될 시작점의 개수를 출력하라.

예제 입력 1

4 5
-1 1
0 -1
0 1
1 0

예제 출력 1

10 16
W3sicHJvYmxlbV9pZCI6IjEyMjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWIxNDBcdWM3NTggXHViOWM4XHVjNzRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlNDBcdWMwYzFcdWFkZmNcdWFjZmMgXHVhZTQwXHVjODE1XHVjNzc4XHVjNzc0IFx1YWRmOFx1YjE0MFx1Yzc1OCBcdWI5YzhcdWM3NGNcdWM3NDQgXHVjNWJiXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjYmRcdWM3YzFcdWM3NDQgXHViYzhjXHVjNzc0XHVhY2UwIFx1Yzc4OFx1YjUzMC4gXHVhZGY4XHViNGU0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzJiOVx1Yzc5MFx1Yjk3YyBcdWFjYjBcdWM4MTVcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzRcdWQ1NWNcdWQ1NWMgXHVkMDZjXHVhZTMwXHVjNzU4IDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0XHVjNWQwIFx1YzViNFx1YjVhNCBcdWM5YzBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhZGY4XHViMTQwXHVhYzAwIFx1YWM3N1x1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjhcdWIxNDBcdWIyOTQgXHVjMGMxLCBcdWQ1NTgsIFx1Yzg4YywgXHVjNmIwIDRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVhYzc4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAgXHVkNTVjXHViYzg4IFx1YWM3OFx1YzViNFx1YWMwOFx1YjU0Y1x1YjljOFx1YjJlNCBcdWI5YzhcdWM3NGNcdWM3NzQgXHViYzE0XHViMDEwXHViMmU0LiBcdWM5ODksIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0XHViYTc0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0XHViYTc0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyZuYnNwO1x1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzVkMFx1YzExY1x1YjI5NCBcdWFkZjhcdWIxNDBcdWFjMDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyAyXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1ZDMxMCBcdWM5MTFcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NzQgXHVjNzg4XHVjNWI0XHVjMTFjIFx1YWRmOFx1YjdmMCBcdWFjZjNcdWM3NDAgXHVjOWMwXHViMDk4XHVhYzAwXHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YjU0YyBcdWFkZjhcdWIxNDBcdWIyOTQmbmJzcDtcdWFkZjggXHVjMmRjXHVjNzkxXHVjODEwXHVjNWQwXHVjMTFjICgwLCAwKVx1YWU0Y1x1YzljMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NDQgXHVkNTNjXHVkNTU4XHVjNWVjIFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yjg1YyBcdWFjNzhcdWM1YjRcdWM2MjhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWIxNDBcdWFjMDAgXHViYjM0XHVkNTVjXHVkNTVjIFx1Y2NiNFx1YjgyNVx1Yzc0NCBcdWFjMDBcdWM5YzQgXHVhYzgzXHVjNzQwIFx1YzU0NFx1YjJjOFx1YmJjMFx1Yjg1YyBcdWFkZjhcdWIxNDBcdWFjMDAgXHVhYzc3XHViMjk0IFx1YWM3OFx1Yzc0Y1x1YzIxOFx1Yjk3YyBTXHVhYzc4XHVjNzRjIFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWM4MWNcdWQ1NWNcdWQ1NjAgXHViNTRjIDJcdWNjMjhcdWM2ZDAgXHVjODhjXHVkNDVjIFx1YzkxMSBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHVhZGY4XHViMTQwXHVhYzAwICgwLCAwKVx1YzVkMCBcdWM2NTRcdWM3NDRcdWI1NGMgXHVjMGMxXHVhZGZjXHVjNzc0XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWM4YyBcdWI0MjAgXHVjMmRjXHVjNzkxXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHVhYzhjIFx1YjQyMCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1YWMxY1x1YzIxOCBCXHVjNjQwIFx1YWM3OFx1Yzc0Y1x1YzIxOCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+KDEmbHQ7PUImbHQ7PTEwMDAwLCAxJmx0Oz1TJmx0Oz0xMDAwMDAwMCkmbmJzcDs8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWFkZjhcdWI5YWNcdWFjZTAgXHViMmU0XHVjNzRjIEJcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCB4LCB5XHVhYzEyXHVjNzU4IFx1YzgwOFx1YjMwMFx1YWMxMlx1Yzc0MCAxMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuPFwvc3Bhbj48XC9wPlxyXG5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWFjOGMgXHViNDIwIFx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVjODE1XHVjNzc4XHVjNzc0XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWM4YyBcdWI0MjAgXHVjMmRjXHVjNzkxXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTIyNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNBQk9SIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgcHJlc2lkZW50IG9mIHRoZSBwb2xpdGljYWwgcGFydHkgaW4gcG93ZXIgaXMgaG9sZGluZyBhIGNvbmZlcmVuY2UgaW4gdGhlIHBhcnR5IGhlYWRxdWFydGVycy48XC9wPlxyXG5cclxuPHA+UG9saXRpY2lhbnMsIG1lbWJlcnMgb2YgdGhlIHBhcnR5LCBsaXZlIGluIGEgdHdvLWRpbWVuc2lvbmFsIGdyaWQsIG9uZSBtZW1iZXIgaW4gZWFjaCBjZWxsIChleGNlcHQgaW4gY2VsbHMgY29udGFpbmluZyBvYnN0YWNsZXMpLiBUaGUgaGVhZHF1YXJ0ZXJzIGFyZSBsb2NhdGVkIGluIGNlbGwgKDAsIDApLiBUaGlzIGlzIGFsc28gd2hlcmUgdGhlIHByZXNpZGVudCBvZiB0aGUgcGFydHkgbGl2ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlBvbGl0aWNpYW5zIG1ha2Ugc3RlcHMgaW4gb25lIG9mIHRoZSBmb3VyIGRpcmVjdGlvbnMgKHVwLCBkb3duLCBsZWZ0LCByaWdodCksIG1vdmluZyB0byBvbmUgb2YgdGhlIGZvdXIgYWRqYWNlbnQgY2VsbHMgaW4gb25lIHN0ZXAuIFRoZXkgY2FuJiMzOTt0IGVudGVyIGNlbGxzIHdpdGggb2JzdGFjbGVzLiBUaGUgY29uZmVyZW5jZSB3aWxsIGJlIGF0dGVuZGVkIGJ5IGFsbCBwYXJ0eSBtZW1iZXJzIHRoYXQgY2FuIHJlYWNoIGhlYWRxdWFydGVycyBpbiBTIHN0ZXBzIG9yIGxlc3MuIEVhY2ggbWVtYmVyIGNvbWluZyB0byB0aGUgY29uZmVyZW5jZSB3aWxsIHRha2UgdGhlIHNob3J0ZXN0IHJvdXRlIHRvIGhlYWRxdWFydGVycyAob3IgYW55IHN1Y2ggcm91dGUsIGlmIHRoZXJlIGlzIG1vcmUgdGhhbiBvbmUpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgcHJlc2lkZW50IGhhcyBvYnNlcnZlZCB0aGF0IHBvbGl0aWNpYW5zIGNoYW5nZSB0aGVpciBwYXJ0eSBhZmZpbGlhdGlvbiB3aXRoIGVhY2ggc3RlcCB0aGV5IHRha2UsIGJlY29taW5nIGEgbWVtYmVyIG9mIHRoZSBvdGhlciBwYXJ0eSAodGhlcmUgYXJlIG9ubHkgdHdvIHBhcnRpZXMgb24gdGhlIHBvbGl0aWNhbCBzY2VuZSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgaG93IG1hbnkgcG9saXRpY2lhbnMgY29tZSB0byB0aGUgY29uZmVyZW5jZSBhcyBtZW1iZXJzIG9mIHRoZSBwYXJ0eSBpbiBwb3dlciwgYW5kIGhvdyBtYW55IGNvbWUgYXMgbWVtYmVycyBvZiB0aGUgb3Bwb3NpbmcgcGFydHkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgQiBhbmQgUyAoMCAmbGU7IEIgJmxlOyAxMCAwMDAsIDEgJmxlOyBTICZsZTsgMTAgMDAwIDAwMCksIHRoZSBudW1iZXIgb2Ygb2JzdGFjbGVzIGFuZCB0aGUgbGFyZ2VzdCBudW1iZXIgb2Ygc3RlcHMgZnJvbSB0aGUgdGFzayBkZXNjcmlwdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEIgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzLCB0aGUgY29vcmRpbmF0ZXMgb2Ygb25lIG9ic3RhY2xlLiBUaGUgYWJzb2x1dGUgdmFsdWUgb2YgYm90aCBjb29yZGluYXRlcyB3aWxsIGJlIGxlc3MgdGhhbiAxMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ObyB0d28gb2JzdGFjbGVzIHdpbGwgYmUgaW4gdGhlIHNhbWUgY2VsbCBhbmQgdGhlcmUgd2lsbCBiZSBubyBvYnN0YWNsZSBpbiBjZWxsICgwLCAwKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdHdvIGludGVnZXJzIG9uIGEgc2luZ2xlIGxpbmUgc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIHRoZSBudW1iZXIgb2YgcG9saXRpY2lhbnMgdGhhdCBjb21lIHRvIHRoZSBjb25mZXJlbmNlIGFzIG1lbWJlcnMgb2YgdGhlIHBhcnR5IGluIHBvd2VyIGFuZCB0aGUgb3Bwb3NpbmcgcGFydHksIHJlc3BlY3RpdmVseS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=