시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB93942935048.209%

문제

오늘은 기초컴퓨터그래픽스의 퀴즈가 있는 날이다. 기다란 교실 안에는 N개의 책상이 한 줄로 늘어서 있는데, 각 책상당 두 명의 학생이 앉도록 되어있다.

모든 학생들은 그래픽스를  열심히 공부했지만, 말도 안되는 난이도에 질려 포기하고 말았다. 한편 교수님은 각 학생들의 얼굴만 보고도 이 학생이 받아야 할 그레이드를 정확히 알아낼 수 있다.

교수님은 그래픽스 과목을 가르치는 만큼 자신의 미적 감각을 살리기 위해 각 그레이드를 다른 색을 이용해서 표시한다(예를 들어 A를 빨강으로 칠하면, B,C,D는 빨강으로 표시하지 않는다).

또, 퀴즈의 방식은 교수님이 수업이 시작할 때 어떤 두 책상을 선택하고, 두 책상과 그 사이에 있는 모든 책상에서 각각 한 명씩 지목해서 질문을 하고, 학생의 대답을 듣는 것이다.

오늘 교수님은 바쁜 나머지 한 가지 색의 색연필만 가지고 왔고, 결국 자신의 미학을 지키기 위해 퀴즈에서 지목한 모두에게 같은 그레이드를 주려고 한다. 교수님이 채점할 수 있는 학생의 수는 최대 몇 명일까?

입력

입력의 첫 번째 줄에는 정수 N이 주어진다(1 ≤ N ≤ 100,000).

다음 N개의 줄에는 i번째 책상에 앉은 두 학생이 받아야 할 그레이드 Ai와 Bi(1 ≤ Ai, Bi ≤ 5)가 주어진다.

출력

교수님이 한 가지 색만을 이용해 채점할 수 있는 최대 학생 수와 그때의 그레이드를 출력한다.

만약 답이 여러 가지라면, 가장 작은 그레이드를 출력한다.

예제 입력 1

1
1 5

예제 출력 1

1 1

예제 입력 2

3
3 5
4 5
1 3

예제 출력 2

2 5

예제 입력 3

4
2 1
3 2
5 3
2 5

예제 출력 3

2 2
W3sicHJvYmxlbV9pZCI6IjI4NzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI3OThcdWQ1M2RcdWMyYTQgXHVkMDM0XHVjOTg4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVhZTMwXHVjZDA4XHVjZWY0XHVkNGU4XHVkMTMwXHVhZGY4XHViNzk4XHVkNTNkXHVjMmE0XHVjNzU4IFx1ZDAzNFx1Yzk4OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHViMGEwXHVjNzc0XHViMmU0LiZuYnNwO1x1YWUzMFx1YjJlNFx1Yjc4MCBcdWFkNTBcdWMyZTQgXHVjNTQ4XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjYzQ1XHVjMGMxXHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHViMjk4XHVjNWI0XHVjMTFjIFx1Yzc4OFx1YjI5NFx1YjM3MCwmbmJzcDtcdWFjMDEgXHVjYzQ1XHVjMGMxXHViMmY5IFx1YjQ1MCBcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzU0OVx1YjNjNFx1Yjg1ZCBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVhZGY4XHViNzk4XHVkNTNkXHVjMmE0XHViOTdjICZuYnNwO1x1YzVmNFx1YzJlY1x1ZDc4OCZuYnNwO1x1YWNmNVx1YmQ4MFx1ZDU4OFx1YzljMFx1YjljYywmbmJzcDtcdWI5ZDBcdWIzYzQgXHVjNTQ4XHViNDE4XHViMjk0IFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YzVkMCBcdWM5YzhcdWI4MjQgXHVkM2VjXHVhZTMwXHVkNTU4XHVhY2UwIFx1YjlkMFx1YzU1OFx1YjJlNC4gXHVkNTVjXHVkM2I4Jm5ic3A7XHVhZDUwXHVjMjE4XHViMmQ4XHVjNzQwIFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjNWJjXHVhZDc0XHViOWNjIFx1YmNmNFx1YWNlMFx1YjNjNCBcdWM3NzQgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmMxYlx1YzU0NFx1YzU3YyBcdWQ1NjAgXHVhZGY4XHViODA4XHVjNzc0XHViNGRjXHViOTdjJm5ic3A7XHVjODE1XHVkNjU1XHVkNzg4IFx1YzU0Y1x1YzU0NFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkNTBcdWMyMThcdWIyZDhcdWM3NDAgXHVhZGY4XHViNzk4XHVkNTNkXHVjMmE0IFx1YWNmY1x1YmFhOVx1Yzc0NCBcdWFjMDBcdWI5NzRcdWNlNThcdWIyOTQgXHViOWNjXHVkMDdjIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJiZjhcdWM4MDEgXHVhYzEwXHVhYzAxXHVjNzQ0IFx1YzBiNFx1YjlhY1x1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzAxIFx1YWRmOFx1YjgwOFx1Yzc3NFx1YjRkY1x1Yjk3YyBcdWIyZTRcdWI5NzggXHVjMGM5XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyZuYnNwO1x1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNChcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IEFcdWI5N2MgXHViZTY4XHVhYzE1XHVjNzNjXHViODVjIFx1Y2U2MFx1ZDU1OFx1YmE3NCwgQixDLERcdWIyOTQgXHViZTY4XHVhYzE1XHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpLjxcL3A+XHJcblxyXG48cD5cdWI2MTAsIFx1ZDAzNFx1Yzk4OFx1Yzc1OCBcdWJjMjlcdWMyZGRcdWM3NDAgXHVhZDUwXHVjMjE4XHViMmQ4XHVjNzc0IFx1YzIxOFx1YzVjNVx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjJm5ic3A7XHVjNWI0XHViNWE0IFx1YjQ1MCBcdWNjNDVcdWMwYzFcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwLCBcdWI0NTAgXHVjYzQ1XHVjMGMxXHVhY2ZjIFx1YWRmOCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWNjNDVcdWMwYzFcdWM1ZDBcdWMxMWMgXHVhYzAxXHVhYzAxIFx1ZDU1YyBcdWJhODVcdWM1MjkgXHVjOWMwXHViYWE5XHVkNTc0XHVjMTFjIFx1YzljOFx1YmIzOFx1Yzc0NCBcdWQ1NThcdWFjZTAsIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWIzMDBcdWIyZjVcdWM3NDQgXHViNGUzXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViMjk4Jm5ic3A7XHVhZDUwXHVjMjE4XHViMmQ4XHVjNzQwIFx1YmMxNFx1YzA1YyBcdWIwOThcdWJhMzhcdWM5YzAgXHVkNTVjIFx1YWMwMFx1YzljMCBcdWMwYzlcdWM3NTggXHVjMGM5XHVjNWYwXHVkNTQ0XHViOWNjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM2NTRcdWFjZTAsJm5ic3A7XHVhY2IwXHVhZDZkIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJiZjhcdWQ1NTlcdWM3NDQgXHVjOWMwXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQwMzRcdWM5ODhcdWM1ZDBcdWMxMWMgXHVjOWMwXHViYWE5XHVkNTVjJm5ic3A7XHViYWE4XHViNDUwXHVjNWQwXHVhYzhjIFx1YWMxOVx1Yzc0MCBcdWFkZjhcdWI4MDhcdWM3NzRcdWI0ZGNcdWI5N2MgXHVjOGZjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZDUwXHVjMjE4XHViMmQ4XHVjNzc0IFx1Y2M0NFx1YzgxMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWJhODVcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDtcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHVjYzQ1XHVjMGMxXHVjNWQwIFx1YzU0OVx1Yzc0MCBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YmMxYlx1YzU0NFx1YzU3YyBcdWQ1NjAgXHVhZGY4XHViODA4XHVjNzc0XHViNGRjJm5ic3A7QTxzdWI+aTxcL3N1Yj5cdWM2NDAgQjxzdWI+aTxcL3N1Yj4oMSAmbGU7IEE8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPiAmbGU7IDUpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFkNTBcdWMyMThcdWIyZDhcdWM3NzQgXHVkNTVjIFx1YWMwMFx1YzljMCBcdWMwYzlcdWI5Y2NcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1Y2M0NFx1YzgxMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NTlcdWMwZGQgXHVjMjE4XHVjNjQwIFx1YWRmOFx1YjU0Y1x1Yzc1OCBcdWFkZjhcdWI4MDhcdWM3NzRcdWI0ZGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhZGY4XHViODA4XHVjNzc0XHViNGRjXHViOTdjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4NzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQUk9GRVNPUiIsImRlc2NyaXB0aW9uIjoiPHA+SW4gYSBsb25nIGNsYXNzcm9vbSwgTiBkZXNrcyBhcmUgYXJyYW5nZWQgaW4gYSBzaW5nbGUgcm93LCB3aXRoIHR3byBzdHVkZW50cyBzaXR0aW5nIGF0IGVhY2ggZGVzay4gU3R1ZGVudHMgYXJlIGNyYW5reSBiZWNhdXNlIHRoZXkgYXJlIGFib3V0IHRvIGhhdmUgYW4gYXJ0IGNsYXNzLCBhbmQgdGhlaXIgcHJvZmVzc29yIGlzIHBsYW5uaW5nIHRvIGV4YW1pbmUgdGhlbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBzdHVkZW50IGhhcyBzdHVkaWVkIGFydCwgYnV0IG9ubHkgdG8gYSBjZXJ0YWluIGxldmVsLiBUaGUgb2xkIHByb2Zlc3NvciBjYW4gdGVsbCBieSB0aGUgbG9va3Mgb24gdGhlaXIgZmFjZXMganVzdCBob3cgbXVjaCB0aGV5IGhhdmUgc3R1ZGllZC4gVGhlIHByb2Zlc3NvciwgYmVpbmcgYW4gYXJ0aXN0LCB1c2VzIGEgZGlmZmVyZW50IGNvbG91cmVkIHBlbmNpbCBmb3IgZWFjaCBncmFkZS4gVW5mb3J0dW5hdGVseSwgdG9kYXkgaGUgYnJvdWdodCBvbmx5IG9uZSBwZW5jaWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIG1ha2UgdGhlIGV4YW1pbmF0aW9uIHNlZW0gZmFpciwgaGUgd2FudHMgdG8gY2hvb3NlIHR3byBkZXNrcyBhbmQgcXVlc3Rpb24gb25lIHN0dWRlbnQgZnJvbSBlYWNoIGRlc2sgcG9zaXRpb25lZCBiZXR3ZWVuIHRoZSB0d28gZGVza3MgaGUgaGFzIGNob3NlbiAoaW5jbHVkaW5nIHRoZSBjaG9zZW4gZGVza3MpLiBJdCBpcyBpbXBvcnRhbnQgdGhhdCBhbGwgZXhhbWluZWQgc3R1ZGVudHMgZGVzZXJ2ZSB0aGUgc2FtZSBncmFkZXMsIHNvIGhlIGNhbiB3cml0ZSB0aGVtIGRvd24gdXNpbmcgaGlzIG9ubHkgcGVuY2lsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgcHJvZmVzc29yIHdhbnRzIHRvIGtub3cgdGhlIG1heGltdW0gbnVtYmVyIG9mIHN0dWRlbnRzIGhlIGNhbiBleGFtaW5lIHRoaXMgd2F5LCBhcyB3ZWxsIGFzIHdoaWNoIGdyYWRlIHRoZSBzdHVkZW50cyB3aWxsIGdldC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gcm93cyBjb250YWlucyB0d28gaW50ZWdlcnM6IEE8c3ViPmk8XC9zdWI+IGFuZCBCPHN1Yj5pPFwvc3ViPiwgZ3JhZGVzIGRlc2VydmVkIGJ5IHN0dWRlbnRzIHNpdHRpbmcgYXQgZGVzayBpICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgNSkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0d28gbnVtYmVycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2U6IHRoZSBtYXhpbXVtIG51bWJlciBvZiBzdHVkZW50cyB0aGUgcHJvZmVzc29yIGNhbiBleGFtaW5lIGFuZCB0aGUgZ3JhZGUgdGhvc2Ugc3R1ZGVudHMgd2lsbCBnZXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBtdWx0aXBsZSBzb2x1dGlvbnMgcG9zc2libGUsIG91dHB1dCB0aGUgb25lIHdpdGggdGhlIHNtYWxsZXN0IGdyYWRlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #1 2번