시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB70000.000%

문제

테트리스보다 약간 인기가 마이너한 삼트리스 게임에 대해 알아보자. 이 게임에서는 3×1 크기의 막대기만이 등장하고, 화면은 가로 7열이다. 막대기는 화면의 제일 위에서 등장해 아래로 내려오며, 회전시킬 수 있다. 내려오다가 바로 아래 칸이 바닥이거나 내려가야 할 자리에 이미 다른 블록이 존재한다면 그 자리에서 멈추게 된다.

이 게임의 목표 또한 테트리스와는 조금 다르다. 화면에 지정된 N개의 칸을 모두 막대기로 채워 넣으면 게임은 끝난다. 이때 최소 개수의 막대기를 사용하고 싶다. 첫 번째 예제를 나타내면 아래 그림과 같다.

입력

첫째 줄에 목표가 되는 칸의 개수 N이 주어진다. (1 ≤ N ≤ 200)

둘째 줄부터 각 칸의 위치가 열 번호, 행 번호 순으로 주어진다. 열 번호는 1 이상 7 이하의 정수이고, 행 번호는 1 이상 108 이하의 정수이다. 화면에서 제일 아래 칸의 행 번호는 1이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

4
1 4
3 4
6 2
7 1

예제 출력 1

4

예제 입력 2

7
5 4
2 4
6 4
1 4
7 4
3 4
4 4

예제 출력 2

6
W3sicHJvYmxlbV9pZCI6IjE0MTI1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGJjXHVkMmI4XHViOWFjXHVjMmE0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTRcdWJjZjRcdWIyZTQgXHVjNTdkXHVhYzA0IFx1Yzc3OFx1YWUzMFx1YWMwMCBcdWI5YzhcdWM3NzRcdWIxMDhcdWQ1NWMgXHVjMGJjXHVkMmI4XHViOWFjXHVjMmE0IFx1YWM4Y1x1Yzc4NFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNTRjXHVjNTQ0XHViY2Y0XHVjNzkwLiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjXHViMjk0IDMmdGltZXM7MSBcdWQwNmNcdWFlMzBcdWM3NTggXHViOWM5XHViMzAwXHVhZTMwXHViOWNjXHVjNzc0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YWNlMCwgXHVkNjU0XHViYTc0XHVjNzQwIFx1YWMwMFx1Yjg1YyA3XHVjNWY0XHVjNzc0XHViMmU0LiBcdWI5YzlcdWIzMDBcdWFlMzBcdWIyOTQgXHVkNjU0XHViYTc0XHVjNzU4IFx1YzgxY1x1Yzc3YyBcdWM3MDRcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTc0IFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWIwYjRcdWI4MjRcdWM2MjRcdWJhNzAsIFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIwYjRcdWI4MjRcdWM2MjRcdWIyZTRcdWFjMDAgXHViYzE0XHViODVjIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3NzQgXHViYzE0XHViMmU1XHVjNzc0XHVhYzcwXHViMDk4IFx1YjBiNFx1YjgyNFx1YWMwMFx1YzU3YyBcdWQ1NjAgXHVjNzkwXHViOWFjXHVjNWQwIFx1Yzc3NFx1YmJmOCBcdWIyZTRcdWI5NzggXHViZTE0XHViODVkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjIFx1YmE0OFx1Y2Q5NFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NTggXHViYWE5XHVkNDVjIFx1YjYxMFx1ZDU1YyBcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTRcdWM2NDBcdWIyOTQgXHVjODcwXHVhZTA4IFx1YjJlNFx1Yjk3NFx1YjJlNC4gXHVkNjU0XHViYTc0XHVjNWQwIFx1YzljMFx1YzgxNVx1YjQxYyBOXHVhYzFjXHVjNzU4IFx1Y2U3OFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWM5XHViMzAwXHVhZTMwXHViODVjIFx1Y2M0NFx1YzZjYyBcdWIxMjNcdWM3M2NcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NTggXHViOWM5XHViMzAwXHVhZTMwXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3NCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTQxMjVcLyVFQyU4QSVBNCVFRCU4MSVBQyVFQiVBNiVCMCVFQyU4MyVCNyUyMDIwMTctMDEtMDIlMjAlRUMlOTglQTQlRUQlOUIlODQlMjA2LjE1LjA5LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0N3B4OyB3aWR0aDozNjRweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYTlcdWQ0NWNcdWFjMDAgXHViNDE4XHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDIwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM1ZjQgXHViYzg4XHVkNjM4LCBcdWQ1ODkgXHViYzg4XHVkNjM4IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVmNCBcdWJjODhcdWQ2MzhcdWIyOTQgMSBcdWM3NzRcdWMwYzEgNyBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHVhY2UwLCBcdWQ1ODkgXHViYzg4XHVkNjM4XHViMjk0IDEgXHVjNzc0XHVjMGMxIDEwPHN1cD44PFwvc3VwPiBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWQ2NTRcdWJhNzRcdWM1ZDBcdWMxMWMgXHVjODFjXHVjNzdjIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3NTggXHVkNTg5IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTQxMjUiLCJwcm9ibGVtX2xhbmciOiI0IiwidGl0bGUiOiJUZXRyaXMiLCJkZXNjcmlwdGlvbiI6IjxwPlUgbWFuamUgcG9wdWxhcm5vaiBpbmFcdTAxMGRpY2kgcG9wdWxhcm5lIGlncmUgVGV0cmlzLCBqZWRpbmkgb2JsaWsga29qaSBzZSBwb2phdmxqdWplIGplICZxdW90OyZzY2Fyb247dGFwaVx1MDEwNyZxdW90OyAzJnRpbWVzOzEuIElncmEgc2UgdSBrdmFkcmF0bm9tIHBvbGp1ICZzY2Fyb247aXJpbmUgc2VkYW0gaSBuZW9ncmFuaVx1MDEwZGVuZSB2aXNpbmUuICZTY2Fyb247dGFwaVx1MDEwN2kgc2UgcG9qYXZsanVqdSBuYSB2ZWxpa29qIHZpc2luaS4gTmEgaWdyYVx1MDEwZHUgamUgZGEgb2RhYmVyZSBvcmlqZW50YWNpanUgKGhvcml6b250YWxuYSBpbGkgdmVydGlrYWxuYSkgdGUgJnNjYXJvbjt0YXBpXHUwMTA3IHBvbWFrbmUgbGlqZXZvIGlsaSBkZXNubyBwbyBcdTAxN2VlbGppLiBOYWtvbiB0b2dhICZzY2Fyb247dGFwaVx1MDEwNyBwb1x1MDEwZG5lIHBhZGF0aSByYXZubyBkb2sgbmUgc2xldGkgbmEgbmVraSBkcnVnaSAmc2Nhcm9uO3RhcGlcdTAxMDcgaWxpIG5hIGRubyBwb2xqYSB6YSBpZ3J1LjxcL3A+XHJcblxyXG48cD5JZ3JhIHphdnImc2Nhcm9uO2F2YSBrYWQgc2UgJnNjYXJvbjt0YXBpXHUwMTA3aW1hIHBva3JpamUgTiBwb3NlYm5vIG96bmFcdTAxMGRlbmloIHBvbGphLiBaYSB6YWRhbmUgcG96aWNpamUgb3puYVx1MDEwZGVuaWggcG9samEsIG9kcmVkaXRlIG5ham1hbmppIGJyb2ogJnNjYXJvbjt0YXBpXHUwMTA3YSBwb3RyZWJhbiB6YSB6YXZyJnNjYXJvbjthdmFuamUgaWdyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTQxMjVcLyVFQyU4QSVBNCVFRCU4MSVBQyVFQiVBNiVCMCVFQyU4MyVCNyUyMDIwMTctMDEtMDIlMjAlRUMlOTglQTQlRUQlOUIlODQlMjA2LjE1LjA5LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0N3B4OyB3aWR0aDozNjRweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VSBwcnZvbSByZWR1IG5hbGF6aSBzZSBwcmlyb2RuaSBicm9qIE4gKDEgJmxlOyBOICZsZTsgMjAwKSwgYnJvaiBvem5hXHUwMTBkZW5paCBwb2xqYS48XC9wPlxyXG5cclxuPHA+VSBzbGplZGVcdTAxMDdpaCBOIHJlZG92YSBuYWxhemUgc2UgcG96aWNpamUgb3puYVx1MDEwZGVuaWggcG9samEuIFN2YWtpIHJlZCBzYWRyXHUwMTdlaSBkdmlqZSBrb29yZGluYXRlLCBicm9qIHN0dXBjYSAoMSBkbyA3KSB0ZSByZWRhLiBOYWpkb25qaSByZWQgdSBwb2xqdSB6YSBpZ3J1IG96bmFcdTAxMGRlbiBqZSBicm9qZW0gMS4gS29vcmRpbmF0YSByZWRhIG5lXHUwMTA3ZSBiaXRpIHZlXHUwMTA3YSBvZCAxMDxzdXA+ODxcL3N1cD4gKHN0byBtaWxpanVuYSkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UG90cmVibm8gamUgaXNwaXNhdGkgamVkYW4gYnJvaiwgbmFqbWFuamkgYnJvaiAmc2Nhcm9uO3RhcGlcdTAxMDdhIHBvdHJlYmFuIHphIHphdnImc2Nhcm9uO2F2YW5qZSBpZ3JlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkNyb2F0aWFuIn1d

출처

ICPC > Regionals > Europe > Central European Regional Contest > The Croatian Programming Contest > CPC 2011 G번

  • 문제를 번역한 사람: kks227