시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 42 28 26 66.667%

문제

꿍은 나름 잘생기고 똑똑하지만 여자앞에서면 말을 잘 못하는 안타까운 학생이다. 그러던 그가 어느날 한눈에 반한 여학생이 생겼지만 역시나 그녀에게 다가가지 못했다.

훗날 꿍은 이런 자신을 반성하며 다시 한 번 그녀에게 다가가기로 마음먹었다. 하지만 그 전에, 꿍은 그녀가 원하는 남자 스타일에 맞는 사람으로 나타나기로 하였다. 알고봤더니 그녀는 다양한 스타일의 남자를 좋아하지만 선택적인 것으로 밝혀졌다. 예를 들어, 그녀는 똑똑하고(intelligent) 세련된(cultivated) 옷을 잘 입는(welldressed) 남자 또는 오토바이를 갖고 있으며(motorcycleowner) 살짝 무뚝뚝한(rude) 남자를 좋아한다. 아니면 단순히 부자(rich)여도 된다.

꿍은 이러한 그녀의 취향에 대한 모든 정보를 적고 그 취향을 만족시키기 위한 계획을 세웠다. 꿍은 각 조건들이 걸리는 시간을 측정하여 어떠한 조합이 가장 시간이 적게 걸리는지 계산만 하면 된다. 이때 꿍은 각 조건들을 병렬적으로 만족시킬 수 있다고 생각한다.

아래 그림을 보자.

[그림: 꿍이 그녀를 정복하기 위해 해야할 것들]

위 그림에서 꿍은 intelligent, cultivated, welldressed 조합을 모두 만족시키는데 걸리는 최소의 시간은 4이다. 왜냐면 꿍은 병렬적으로 조건들을 만족시킬 수 있기 때문이다. 마찬가지 방법으로 따져보면 motorcycleowner, rude 조합을 만족시키는데는 8, rich 조합은 100의 시간이 걸린다. 이 세 가지 조합 중 가장 시간이 적게 걸리는 조합은 intelligent, cultivated, welldressed 조합이다.

입력

첫 번째 줄에는 테스트케이스의 개수가 주어진다 (최댓값=100).

각 테스트케이스는 두 줄의 문자열이 주어진다.

첫 번째 문자열은 각 조건을 만족시키는데 걸리는 시간이 ','(쉼표)에 의해 구분되어 주어지며 조건의 이름, 콜론(:), 그리고 걸리는 시간으로 구성되어 있다. 조건의 이름은 a부터 z까지로만 이루어져 있으며 길이는 1부터 20이다. 비용은 0부터 1000까지 각각 주어지며 조건의 개수는 20을 넘지 않는다.

두 번째 문자열은 그녀를 만족시키는데 필요한 조건의 조합들이 주어진다. 각 조합은 '&'기호와 '|'기호로 구분되어 주어진다. 조합의 개수는 10을 넘지 않으며 각 조합은 최소 한 가지의 조건이 포함되어 있으며 같은 조건이 두번이상 나오지 않는다.

출력

각 테스트케이스에 대해 그녀의 조건을 만족시키는데 걸리는 최소의 시간을 출력한다.

예제 입력 1

3
intelligent:0,cultivated:4,welldressed:2,motorcycleowner:3,rude:8,rich:100
intelligent&cultivated&welldressed|motorcycleowner&rude|rich
ab:13,b:17,cab:21
ab&b|b&cab
a:14,b:13,c:14,d:11
a&b&c|d&a&c|a|b&d

예제 출력 1

4
17
13

힌트

(조합1) | (조합2) | (조합3) .... 이런 식으로 구성되어있다고 보면 편하다.

W3sicHJvYmxlbV9pZCI6IjExMTAxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZmNkXHVjNzU4IFx1YzVlY1x1Y2U1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWZjZFx1Yzc0MCBcdWIwOThcdWI5ODQgXHVjNzk4XHVjMGRkXHVhZTMwXHVhY2UwIFx1YjYxMVx1YjYxMVx1ZDU1OFx1YzljMFx1YjljYyBcdWM1ZWNcdWM3OTBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJhNzQmbmJzcDtcdWI5ZDBcdWM3NDQgXHVjNzk4Jm5ic3A7XHViYWJiXHVkNTU4XHViMjk0IFx1YzU0OFx1ZDBjMFx1YWU0Y1x1YzZiNCBcdWQ1NTlcdWMwZGRcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjM1OCBcdWFkZjhcdWFjMDAgXHVjNWI0XHViMjkwXHViMGEwIFx1ZDU1Y1x1YjIwOFx1YzVkMCBcdWJjMThcdWQ1NWMgXHVjNWVjXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzBkZFx1YWNiY1x1YzljMFx1YjljYyBcdWM1ZWRcdWMyZGNcdWIwOTggXHVhZGY4XHViMTQwXHVjNWQwXHVhYzhjIFx1YjJlNFx1YWMwMFx1YWMwMFx1YzljMCBcdWJhYmJcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDZkN1x1YjBhMCBcdWFmY2RcdWM3NDAgXHVjNzc0XHViN2YwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWJjMThcdWMxMzFcdWQ1NThcdWJhNzAgXHViMmU0XHVjMmRjIFx1ZDU1YyBcdWJjODggXHVhZGY4XHViMTQwXHVjNWQwXHVhYzhjIFx1YjJlNFx1YWMwMFx1YWMwMFx1YWUzMFx1Yjg1YyBcdWI5YzhcdWM3NGNcdWJhMzlcdWM1YzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWFkZjggXHVjODA0XHVjNWQwLCBcdWFmY2RcdWM3NDAgXHVhZGY4XHViMTQwXHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWIwYThcdWM3OTAgXHVjMmE0XHVkMGMwXHVjNzdjXHVjNWQwIFx1YjlkZVx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMDk4XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVjNTRjXHVhY2UwXHViZDI0XHViMzU0XHViMmM4IFx1YWRmOFx1YjE0MFx1YjI5NCBcdWIyZTRcdWM1OTFcdWQ1NWMgXHVjMmE0XHVkMGMwXHVjNzdjXHVjNzU4IFx1YjBhOFx1Yzc5MFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjMTIwXHVkMGRkXHVjODAxXHVjNzc4IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWJjMWRcdWQ2MDBcdWM4NGNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWRmOFx1YjE0MFx1YjI5NCBcdWI2MTFcdWI2MTFcdWQ1NThcdWFjZTAoaW50ZWxsaWdlbnQpIFx1YzEzOFx1YjgyOFx1YjQxYyhjdWx0aXZhdGVkKSBcdWM2MzdcdWM3NDQgXHVjNzk4IFx1Yzc4NVx1YjI5NCh3ZWxsZHJlc3NlZCkgXHViMGE4XHVjNzkwIFx1YjYxMFx1YjI5NCBcdWM2MjRcdWQxYTBcdWJjMTRcdWM3NzRcdWI5N2MgXHVhYzE2XHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3MChtb3RvcmN5Y2xlb3duZXIpIFx1YzBiNFx1YzlkZCBcdWJiMzRcdWI2OWRcdWI2OWRcdWQ1NWMocnVkZSkgXHViMGE4XHVjNzkwXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViMmM4XHViYTc0IFx1YjJlOFx1YzIxY1x1ZDc4OCBcdWJkODBcdWM3OTAocmljaClcdWM1ZWNcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFmY2RcdWM3NDAgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWRmOFx1YjE0MFx1Yzc1OCBcdWNkZThcdWQ1YTVcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjODAxXHVhY2UwIFx1YWRmOCBcdWNkZThcdWQ1YTVcdWM3NDQgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVjMTM4XHVjNmUwXHViMmU0LiZuYnNwO1x1YWZjZFx1Yzc0MCBcdWFjMDEgXHVjODcwXHVhYzc0XHViNGU0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZTIxXHVjODE1XHVkNTU4XHVjNWVjIFx1YzViNFx1YjVhMFx1ZDU1YyBcdWM4NzBcdWQ1NjlcdWM3NzQgXHVhYzAwXHVjN2E1IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM4MDFcdWFjOGMgXHVhYzc4XHViOWFjXHViMjk0XHVjOWMwIFx1YWNjNFx1YzBiMFx1YjljYyBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVhZmNkXHVjNzQwIFx1YWMwMSBcdWM4NzBcdWFjNzRcdWI0ZTRcdWM3NDQgXHViY2QxXHViODJjXHVjODAxXHVjNzNjXHViODVjIFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPjxpbWcgc3JjPVwiXC91c2VydXBsb2FkXC9zZW9rOTMxMVwvMjAxNTEyXC81MjY2YmVjODhkZTg3YmRlYTQwMGYwM2Q4M2QyYzcxYS5wbmdcIiBzdHlsZT1cImhlaWdodDoyODNweDsgd2lkdGg6NDQzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+W1x1YWRmOFx1YjliYzogXHVhZmNkXHVjNzc0IFx1YWRmOFx1YjE0MFx1Yjk3YyBcdWM4MTVcdWJjZjVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU3NFx1YzU3Y1x1ZDU2MCBcdWFjODNcdWI0ZTRdPFwvcD5cclxuXHJcbjxwPlx1YzcwNCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVhZmNkXHVjNzQwIGludGVsbGlnZW50LCBjdWx0aXZhdGVkLCB3ZWxsZHJlc3NlZCBcdWM4NzBcdWQ1NjlcdWM3NDQgXHViYWE4XHViNDUwIFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc0MCA0XHVjNzc0XHViMmU0LiBcdWM2NWNcdWIwZDBcdWJhNzQgXHVhZmNkXHVjNzQwIFx1YmNkMVx1YjgyY1x1YzgwMVx1YzczY1x1Yjg1YyBcdWM4NzBcdWFjNzRcdWI0ZTRcdWM3NDQgXHViOWNjXHVjODcxXHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YjUzMFx1YzgzOFx1YmNmNFx1YmE3NCBtb3RvcmN5Y2xlb3duZXIsIHJ1ZGUgXHVjODcwXHVkNTY5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NFx1YjM3MFx1YjI5NCA4LCByaWNoIFx1Yzg3MFx1ZDU2OVx1Yzc0MCAxMDBcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC4gXHVjNzc0IFx1YzEzOCBcdWFjMDBcdWM5YzAgXHVjODcwXHVkNTY5IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzgwMVx1YWM4YyBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzQwIGludGVsbGlnZW50LCBjdWx0aXZhdGVkLCB3ZWxsZHJlc3NlZCBcdWM4NzBcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoXHVjZDVjXHViMzEzXHVhYzEyPTEwMCkuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWFjMDEgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0ICYjMzk7LCYjMzk7KFx1YzI3Y1x1ZDQ1YylcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHVjODcwXHVhYzc0XHVjNzU4IFx1Yzc3NFx1Yjk4NCwgXHVjZjVjXHViODYwKDopLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1YzczY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM4NzBcdWFjNzRcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIGFcdWJkODBcdWQxMzAgelx1YWU0Y1x1YzljMFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwIFx1YWUzOFx1Yzc3NFx1YjI5NCAxXHViZDgwXHVkMTMwIDIwXHVjNzc0XHViMmU0LiBcdWJlNDRcdWM2YTlcdWM3NDAgMFx1YmQ4MFx1ZDEzMCAxMDAwXHVhZTRjXHVjOWMwIFx1YWMwMVx1YWMwMSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAgXHVjODcwXHVhYzc0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAyMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWFkZjhcdWIxNDBcdWI5N2MgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM4NzBcdWFjNzRcdWM3NTggXHVjODcwXHVkNTY5XHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1Yzg3MFx1ZDU2OVx1Yzc0MCAmIzM5OyZhbXA7JiMzOTtcdWFlMzBcdWQ2MzhcdWM2NDAgJiMzOTt8JiMzOTtcdWFlMzBcdWQ2MzhcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODcwXHVkNTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwIFx1YWMwMSBcdWM4NzBcdWQ1NjlcdWM3NDAgXHVjZDVjXHVjMThjIFx1ZDU1YyBcdWFjMDBcdWM5YzBcdWM3NTggXHVjODcwXHVhYzc0XHVjNzc0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWI0NTBcdWJjODhcdWM3NzRcdWMwYzEgXHViMDk4XHVjNjI0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWFkZjhcdWIxNDBcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPihcdWM4NzBcdWQ1NjkxKSB8IChcdWM4NzBcdWQ1NjkyKSB8IChcdWM4NzBcdWQ1NjkzKSAuLi4uIFx1Yzc3NFx1YjdmMCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0XHVhY2UwIFx1YmNmNFx1YmE3NCBcdWQzYjhcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTEwMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbnF1aXN0YWRvciIsImRlc2NyaXB0aW9uIjoiPHA+UnVuZSBKb2hhbiBpcyBhIG5pY2UgeW91bmcgYm95IGFuZCBhIGNsZXZlciBzdHVkZW50LCBidXQgaGUgaGFzIGhhZCBsaXR0bGUgbHVjayBlbmdhZ2luZyBwZXJzb25zIG9mIHRoZSBmZW1hbGUgcGVyc3Vhc2lvbiBpbiBmcnVpdGZ1bCBjb252ZXJzYXRpb24uIEhlIHdhcyB2ZXJ5IGdyYXRlZnVsIHdoZW4gdGhlIGNvbXB1dGVyIHNjaWVuY2UgZGVwYXJ0bWVudCBvcmdhbmlzZWQgYSBiYWxsLCBhbmQgaW52aXRlZCB0aGUgZmlyc3QgZ3JhZGUgbnVyc2Ugc3R1ZGVudHMuIFRoZXJlIGhlIHNhdyBoZXIsIHRoZSB3b21hbiBvZiBoaXMgZHJlYW1zLiBCdXQgYXMgbW9zdCBvZiB1cyBkbyBpbiBzdWNoIHNpdHVhdGlvbnMsIGhlIGZyb3plIHVwLCBhbmQgZGlkIG5vdCBkYXJlIHRvIGFwcHJvYWNoIGhlci48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgYSBmZXcgZGF5cyBvZiByZWdyZXR0aW5nIGhpcyBsYWNrIG9mIGFjdGlvbiwgUnVuZSBKb2hhbiBkZWNpZGVzIHRvIG1ha2UgdXAgZm9yIGl0LiBIZSBmaW5kcyBoZXIgbmFtZSwgQ2VsaW5hIE1pZGRsZXdhcmUsIGJ1dCBkb2VzIG5vdCB3YW50IHRvIGNvbnRhY3QgaGVyIGJlZm9yZSBoZSBoYXMgbWFkZSBhIGRlY2VudCBwbGFuLiBIZSBzdGFydHMgYnkgbG9jYXRpbmcgb25lIG9mIGhlciBmcmllbmRzLCBCaiZvc2xhc2g7cmdmcmlkLCBhbmQgaW52aXRlcyBoZXIgdG8gYSBjdXAgb2YgY29mZmVlLiBBZnRlciBhIGZldyBtaW51dGVzIG9mIGNvbnZlcnNhdGlvbiwgQmomb3NsYXNoO3JnZnJpZCB0ZWxscyB0aGF0IHNoZSBoYXMgc29tZSB0cm91YmxlIHdpdGggaGVyIGNvbXB1dGVyLiBSdW5lIEpvaGFuIG1ha2VzIGEgZGVhbCB3aXRoIGhlci4gSGUgd2lsbCBmaXggaGVyIGNvbXB1dGVyIGlmIHNoZSB0ZWxscyBoaW0gZXZlcnl0aGluZyBoZSBuZWVkcyB0byBrbm93IGFib3V0IENlbGluYS48XC9wPlxyXG5cclxuPHA+SXQgdHVybnMgb3V0IHRoYXQgQ2VsaW5hIGxpa2VzIG1hbnkgZGlmZmVyZW50IGtpbmRzIG9mIGJveXMsIGJ1dCBzaGUgaXMgc3RpbGwgcmF0aGVyIHBpY2t5LiBIZSBjb3VsZCBiZSBpbnRlbGxpZ2VudCwgY3VsdGl2YXRlZCBhbmQgd2VsbCBkcmVzc2VkLCBvciBvd24gYSBtb3RvcmN5Y2xlIGFuZCBiZSBzbGlnaHRseSBydWRlLiBPciBoZSBjb3VsZCBzaW1wbHkgYmUgcmljaC4gUnVuZSBKb2hhbiB3cml0ZXMgZG93biBhbGwgdGhlIGluZm9ybWF0aW9uLCBhbmQgZ29lcyBob21lIHRvIGZpbmlzaCBoaXMgcGxhbi4gSGUgbWFrZXMgYW4gZXN0aW1hdGUgb2YgaG93IG1hbnkgd2Vla3MgaXQgd291bGQgdGFrZSB0byBmdWxmaWwgZWFjaCBvZiB0aGUgY3JpdGVyaWEsIGFuZCB0cmllcyB0byBkZWNpZGUgd2hpY2ggY29tYmluYXRpb24gdGFrZXMgbGVzcyB0aW1lLiBIZSB0aGlua3MgdGhhdCBoZSBjYW4gd29yayBvbiBhbGwgb2YgdGhlbSBpbiBwYXJhbGxlbC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTExMDFcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjgzcHg7IHdpZHRoOjQ0M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPkZpZ3VyZSAxOiBXaGF0IFJ1bmUgSm9oYW4gbXVzdCBiZWNvbWUgdG8gY29ucXVlciBDZWxpbmEgTWlkZGxld2FyZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGdpdmVzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgd2hpY2ggaXMgYXQgbW9zdCAxMDAuIEVhY2ggdGVzdCBjYXNlIGlzIGdpdmVuIGFzIHR3byBzdHJpbmdzIG9uIHNlcGFyYXRlIGxpbmVzLiBUaGUgZmlyc3Qgc3RyaW5nIGdpdmVzIHRoZSB0aW1lIGNvc3RzIG9mIGZ1bGZpbGxpbmcgdGhlIGNyaXRlcmlhLCBzZXBhcmF0ZWQgYnkgY29tbWFzLiBFYWNoIGNvc3QgaXMgZ2l2ZW4gYnkgYSBzdHJpbmcgZ2l2aW5nIHRoZSBuYW1lIG9mIHRoZSBjcml0ZXJpb24sIGEgY29sb24sIGFuZCB0aGVuIHRoZSBpbnRlZ2VyIHRpbWUgY29zdCBvZiB0aGUgY3JpdGVyaW9uIGluIHdlZWtzLiBUaGUgbmFtZXMgY29udGFpbiBzeW1ib2xzICZyc3F1bzthJnJzcXVvOyB0byAmcnNxdW87eiZyc3F1bzssIGFuZCB0aGVpciBsZW5ndGggaXMgZnJvbSAxIHRvIDIwLiBUaGUgY29zdHMgYXJlIGJldHdlZW4gMCBhbmQgMTAwMCBpbmNsdXNpdmUuIFRoZXJlIHdpbGwgYmUgbm8gbW9yZSB0aGFuIDIwIGRpZmZlcmVudCBjcml0ZXJpYS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBzdHJpbmcgZ2l2ZXMgdGhlIGNvbWJpbmF0aW9ucyBvZiBjcml0ZXJpYSB3aGljaCB3aWxsIHNhdGlzZnkgbWlzcyBNaWRkbGV3YXJlLiBFYWNoIGNvbWJpbmF0aW9uIGlzIHNlcGFyYXRlZCBieSB0aGUgc3ltYm9sICZyc3F1bzsmYW1wOyZyc3F1bzssIGFuZCB0aGUgY3JpdGVyaWEgYXJlIHNlcGFyYXRlZCBieSB0aGUgc3ltYm9sICZyc3F1bzt8JnJzcXVvOy4gVGhlcmUgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDEwIGNvbWJpbmF0aW9ucyBpbiBlYWNoIHNjZW5hcmlvLiBFYWNoIGNvbWJpbmF0aW9uIHdpbGwgY29udGFpbiBhdCBsZWFzdCBvbmUgY3JpdGVyaW9uLCBhbmQgbmFtZSBubyBjcml0ZXJpb24gbW9yZSB0aGFuIG9uY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBzY2VuYXJpbywgb3V0cHV0IGEgbGluZSB3aXRoIHRoZSBtaW5pbXVtIHRpbWUgY29zdCBpbiB3ZWVrcyBmb3Igc2F0aXNmeWluZyBDZWxpbmEmcnNxdW87cyBkZXNpcmVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > IDI Open Contest > IDI Open 2007 D번