시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 322 79 63 25.301%

문제

어떠한 다이아몬드의 가치는 그 다이아몬드의 중량인 캐럿과 선명도에 의해서 결정됩니다. 즉, 작지만 선명한 다이아몬드가 크고 선명하지 않은 다이아몬드보다는 가치가 높습니다. 다이아몬드의 선명도는 0.0-10.0의 스캐일로 표현할 수 있는데, 0.0의 선명도는 완벽하게 선명한 다이아몬드를 나타내고 10.0은 가장 결함이 많은 다이아몬드를 나타냅니다.

N개의 다이아몬드의 중량 wi와 선명도 ci의 정보가 주어졌을때, 이 중에서 다이아몬드의 가치가 높아지는 부분열중 최장의 것의 길이를 구하세요. 예를들어 주어진 정보가 다음과 같다면

wi ci
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5

다이아몬드의 가치가 높아지는 부분열중 길이가 최장인것은 다음과 같습니다:

1.5 9.0
2.5 6.0
3.0 5.0
4.0 2.0

표에서 볼 수 있듯이, 가치가 높은 다이아몬드일수로 무게의 값은 크고 선명도의 값은 낮습니다.

입력

테스트 케이스의 갯수 T가 주어지고 (1≤T≤100) 각 테스트 케이스마다 다이아몬드의 정보의 갯수 N (1≤N≤200)이 주어집니다. 그리고 N개의 줄에 걸쳐서 다이아몬드의 무게와 선명도 wi, ci가 주어집니다 (0≤wi,ci≤100).

출력

각 테스트 케이스마다 다이아몬드의 가치가 높아지는 부분열중 최장의 것의 길이를 구하세요.

예제 입력 1

3
2
1.0 1.0
1.5 0.0
3
1.0 1.0
1.0 1.0
1.0 1.0
6
1.5 9.0
2.0 2.0
2.5 6.0
3.0 5.0
4.0 2.0
10.0 5.5

예제 출력 1

2
1
4
W3sicHJvYmxlbV9pZCI6IjEwNTcxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZGlhbW9uZC5wbmdcIiBzdHlsZT1cImhlaWdodDo3MnB4OyB3aWR0aDoyMTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTBcdWQ1NWMgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YWMwMFx1Y2U1OFx1YjI5NCBcdWFkZjggXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YzkxMVx1YjdjOVx1Yzc3OCBcdWNlOTBcdWI3ZmZcdWFjZmMgXHVjMTIwXHViYTg1XHViM2M0XHVjNWQwIFx1Yzc1OFx1ZDU3NFx1YzExYyBcdWFjYjBcdWM4MTVcdWI0MjlcdWIyYzhcdWIyZTQuIFx1Yzk4OSwgXHVjNzkxXHVjOWMwXHViOWNjIFx1YzEyMFx1YmE4NVx1ZDU1YyBcdWIyZTRcdWM3NzRcdWM1NDRcdWJhYWNcdWI0ZGNcdWFjMDAgXHVkMDZjXHVhY2UwIFx1YzEyMFx1YmE4NVx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHViY2Y0XHViMmU0XHViMjk0IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWIxOTJcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YjJlNFx1Yzc3NFx1YzU0NFx1YmFhY1x1YjRkY1x1Yzc1OCBcdWMxMjBcdWJhODVcdWIzYzRcdWIyOTQgMC4wLTEwLjBcdWM3NTggXHVjMmE0XHVjZTkwXHVjNzdjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCAwLjBcdWM3NTggXHVjMTIwXHViYTg1XHViM2M0XHViMjk0IFx1YzY0NFx1YmNiZFx1ZDU1OFx1YWM4YyBcdWMxMjBcdWJhODVcdWQ1NWMgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCAxMC4wXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWFjYjBcdWQ1NjhcdWM3NzQgXHViOWNlXHVjNzQwIFx1YjJlNFx1Yzc3NFx1YzU0NFx1YmFhY1x1YjRkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYzVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YzkxMVx1YjdjOSB3PHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWMxMjBcdWJhODVcdWIzYzQgYzxzdWI+aTxcL3N1Yj5cdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YywgXHVjNzc0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWIyZTRcdWM3NzRcdWM1NDRcdWJhYWNcdWI0ZGNcdWM3NTggXHVhYzAwXHVjZTU4XHVhYzAwIFx1YjE5Mlx1YzU0NFx1YzljMFx1YjI5NCBcdWJkODBcdWJkODRcdWM1ZjRcdWM5MTEgXHVjZDVjXHVjN2E1XHVjNzU4IFx1YWM4M1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMTM4XHVjNjk0LiBcdWM2MDhcdWI5N2NcdWI0ZTRcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0XHViYTc0PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcyA9IFwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOiAzMCU7XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+dzxzdWI+aTxcL3N1Yj48XC90ZD5cclxuXHRcdFx0PHRkPmM8c3ViPmk8XC9zdWI+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEuNTxcL3RkPlxyXG5cdFx0XHQ8dGQ+OS4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjIuMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+Mi4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjIuNTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Ni4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjMuMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NS4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQuMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+Mi4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEwLjA8XC90ZD5cclxuXHRcdFx0PHRkPjUuNTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWIxOTJcdWM1NDRcdWM5YzBcdWIyOTQgXHViZDgwXHViZDg0XHVjNWY0XHVjOTExIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWNkNWNcdWM3YTVcdWM3NzhcdWFjODNcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YzJiNVx1YjJjOFx1YjJlNDo8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzID0gXCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6IDMwJTtcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xLjU8XC90ZD5cclxuXHRcdFx0PHRkPjkuMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4yLjU8XC90ZD5cclxuXHRcdFx0PHRkPjYuMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zLjA8XC90ZD5cclxuXHRcdFx0PHRkPjUuMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD40LjA8XC90ZD5cclxuXHRcdFx0PHRkPjIuMDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHVkNDVjXHVjNWQwXHVjMTFjIFx1YmNmYyBcdWMyMTggXHVjNzg4XHViNGVmXHVjNzc0LCBcdWFjMDBcdWNlNThcdWFjMDAgXHViMTkyXHVjNzQwIFx1YjJlNFx1Yzc3NFx1YzU0NFx1YmFhY1x1YjRkY1x1Yzc3Y1x1YzIxOFx1Yjg1YyBcdWJiMzRcdWFjOGNcdWM3NTggXHVhYzEyXHVjNzQwIFx1ZDA2Y1x1YWNlMCBcdWMxMjBcdWJhODVcdWIzYzRcdWM3NTggXHVhYzEyXHVjNzQwIFx1YjBhZVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMmZcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAgKDEmbGU7VCZsZTsxMDApIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjJlNFx1Yzc3NFx1YzU0NFx1YmFhY1x1YjRkY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWM3NTggXHVhYzJmXHVjMjE4IE4gKDEmbGU7TiZsZTsyMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWIyZTRcdWM3NzRcdWM1NDRcdWJhYWNcdWI0ZGNcdWM3NTggXHViYjM0XHVhYzhjXHVjNjQwIFx1YzEyMFx1YmE4NVx1YjNjNCB3PHN1Yj5pLCA8XC9zdWI+YzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0ICgwJmxlO3c8c3ViPmksPFwvc3ViPmM8c3ViPmk8XC9zdWI+JmxlOzEwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViMmU0XHVjNzc0XHVjNTQ0XHViYWFjXHViNGRjXHVjNzU4IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWIxOTJcdWM1NDRcdWM5YzBcdWIyOTQgXHViZDgwXHViZDg0XHVjNWY0XHVjOTExIFx1Y2Q1Y1x1YzdhNVx1Yzc1OCBcdWFjODNcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDU3MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpYW1vbmRzIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZGlhbW9uZC5wbmdcIiBzdHlsZT1cImhlaWdodDo3MnB4OyB3aWR0aDoyMTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BIGRpYW1vbmQmcnNxdW87cyBvdmVyYWxsIHdvcnRoIGlzIGRldGVybWluZWQgYnkgaXRzIG1hc3MgaW4gY2FyYXRzIGFzIHdlbGwgYXMgaXRzIG92ZXJhbGwgY2xhcml0eS4gQSBsYXJnZSBkaWFtb25kIHdpdGggbWFueSBpbXBlcmZlY3Rpb25zIGlzIG5vdCB3b3J0aCBhcyBtdWNoIGFzIGEgc21hbGxlciwgZmxhd2xlc3MgZGlhbW9uZC4gVGhlIG92ZXJhbGwgY2xhcml0eSBvZiBhIGRpYW1vbmQgY2FuIGJlIGRlc2NyaWJlZCBvbiBhIHNjYWxlIGZyb20gMC4wJm5kYXNoOzEwLjAgYWRvcHRlZCBieSB0aGUgQW1lcmljYW4gR2VtIFNvY2lldHksIHdoZXJlIDAuMCByZXByZXNlbnRzIGEgZmxhd2xlc3MgZGlhbW9uZCBhbmQgMTAuMCByZXByZXNlbnRzIGFuIGltcGVyZmVjdCBkaWFtb25kLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHNlcXVlbmNlIG9mIE4gZGlhbW9uZHMsIGVhY2ggd2l0aCB3ZWlnaHQsIHc8c3ViPmk8XC9zdWI+LCBpbiBjYXJhdHMgYW5kIGNsYXJpdHksIGM8c3ViPmk8XC9zdWI+LCBvbiB0aGUgc2NhbGUgZGVzY3JpYmVkIGFib3ZlLCBmaW5kIHRoZSBsb25nZXN0IHN1YnNlcXVlbmNlIG9mIGRpYW1vbmRzIGZvciB3aGljaCB0aGUgd2VpZ2h0IGFuZCBjbGFyaXR5IGFyZSBib3RoIGJlY29taW5nIHN0cmljdGx5IG1vcmUgZmF2b3JhYmxlIHRvIGEgYnV5ZXIuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBmb2xsb3dpbmcgc2VxdWVuY2Ugb2YgZGlhbW9uZHMsPFwvcD5cclxuXHJcbjxwcmU+XHJcbnc8c3ViPmk8XC9zdWI+ICZuYnNwO2M8c3ViPmk8XC9zdWI+XHJcbjEuNSA5LjBcclxuMi4wIDIuMFxyXG4yLjUgNi4wXHJcbjMuMCA1LjBcclxuNC4wIDIuMFxyXG4xMC4wIDUuNTxcL3ByZT5cclxuXHJcbjxwPnRoZSBsb25nZXN0IGRlc2lyYWJsZSBzdWJzZXF1ZW5jZSBpczxcL3A+XHJcblxyXG48cHJlPlxyXG4xLjUgOS4wXHJcbjIuNSA2LjBcclxuMy4wIDUuMFxyXG40LjAgMi4wPFwvcHJlPlxyXG5cclxuPHA+YmVjYXVzZSB0aGUgd2VpZ2h0cyBzdHJpY3RseSBpbmNyZWFzZSB3aGlsZSB0aGUgY2xhcml0aWVzIHN0cmljdGx5IGRlY3JlYXNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgYmVnaW5zIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciBULCAxICZsZTsgVCAmbGU7IDEwMCwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGJlZ2lucyB3aXRoIGEgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgTiwgMSAmbGU7IE4gJmxlOyAyMDAsIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBkaWFtb25kcy4gTmV4dCBmb2xsb3cgTiBsaW5lcyB3aXRoIDIgcmVhbCBudW1iZXJzIHc8c3ViPmk8XC9zdWI+IGFuZCBjPHN1Yj5pPFwvc3ViPiwgMC4wICZsZTsgdzxzdWI+aTxcL3N1Yj4sIGM8c3ViPmk8XC9zdWI+ICZsZTsgMTAuMCwgaW5kaWNhdGluZyB0aGUgd2VpZ2h0IGluIGNhcmF0cyBhbmQgdGhlIGNsYXJpdHkgb2YgZGlhbW9uZCBpLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgbGluZSB3aXRoIHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgZGVzaXJhYmxlIHN1YnNlcXVlbmNlIG9mIGRpYW1vbmRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==