문제
Moloco는 전 세계의 다양한 회사들이 온라인 광고를 더 잘할 수 있도록 돕는 광고 기술 회사이다. Moloco의 기술을 사용하면 인터넷 사용자들이 더 관련성 높은 광고를 볼 수 있게 되고, 광고주들은 효과적으로 광고를 할 수 있다.
Moloco의 자동 광고 배치 시스템은 대기 중인 광고 요청들을 실시간으로 묶어 처리하여 효율을 최적화한다. 각 광고 요청에는 그 요청을 처리할 때의 비용을 나타내는 양의 정수 값이 정해져 있다. 총 $N$개의 광고 요청이 순서대로 대기열에 주어졌을 때, 시스템은 다음 과정을 반복하여 모든 요청을 소화한다.
- 현재 대기열의 앞쪽에서 최대 3개의 광고 요청을 확인한 다음, 그 중 2개의 요청을 선택하여 동시에 처리하고 제거한다. 이때 발생하는 비용은 선택된 두 요청 중 작지 않은 값이다.
- 만약 대기열에 단 하나의 요청만 남아 있다면, 그 요청을 단독 처리하고 제거한다. 이때의 비용은 그 요청의 값이 된다.
시스템이 모든 광고 요청을 처리하기 위해 필요한 총 비용의 최솟값을 구하시오.
출력
각 테스트 케이스에 대해 모든 광고 요청을 처리하기 위해 필요한 총 비용의 최솟값을 $T$개의 줄에 걸쳐 순서대로 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0MDk2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzkwXHViM2Q5IFx1YWQxMVx1YWNlMCBcdWJjMzBcdWNlNTggXHVjMmRjXHVjMmE0XHVkMTVjIiwiZGVzY3JpcHRpb24iOiI8cD5Nb2xvY29cdWIyOTQgXHVjODA0IFx1YzEzOFx1YWNjNFx1Yzc1OCBcdWIyZTRcdWM1OTFcdWQ1NWMgXHVkNjhjXHVjMGFjXHViNGU0XHVjNzc0IFx1YzYyOFx1Yjc3Y1x1Yzc3OCBcdWFkMTFcdWFjZTBcdWI5N2MgXHViMzU0IFx1Yzc5OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YjNkNVx1YjI5NCBcdWFkMTFcdWFjZTAgXHVhZTMwXHVjMjIwIFx1ZDY4Y1x1YzBhY1x1Yzc3NFx1YjJlNC4gTW9sb2NvXHVjNzU4IFx1YWUzMFx1YzIyMFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQgXHVjNzc4XHVkMTMwXHViMTM3IFx1YzBhY1x1YzZhOVx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWIzNTQgXHVhZDAwXHViODI4XHVjMTMxIFx1YjE5Mlx1Yzc0MCBcdWFkMTFcdWFjZTBcdWI5N2MgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWFkMTFcdWFjZTBcdWM4ZmNcdWI0ZTRcdWM3NDAgXHVkNmE4XHVhY2ZjXHVjODAxXHVjNzNjXHViODVjIFx1YWQxMVx1YWNlMFx1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+TW9sb2NvXHVjNzU4IFx1Yzc5MFx1YjNkOSBcdWFkMTFcdWFjZTAgXHViYzMwXHVjZTU4IFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0MCBcdWIzMDBcdWFlMzAgXHVjOTExXHVjNzc4IFx1YWQxMVx1YWNlMCBcdWM2OTRcdWNjYWRcdWI0ZTRcdWM3NDQgXHVjMmU0XHVjMmRjXHVhYzA0XHVjNzNjXHViODVjIFx1YmIzNlx1YzViNCBcdWNjOThcdWI5YWNcdWQ1NThcdWM1ZWMgXHVkNmE4XHVjNzI4XHVjNzQ0IFx1Y2Q1Y1x1YzgwMVx1ZDY1NFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YWQxMVx1YWNlMCBcdWM2OTRcdWNjYWRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YzY5NFx1Y2NhZFx1Yzc0NCBcdWNjOThcdWI5YWNcdWQ1NjAgXHViNTRjXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWFjMTJcdWM3NzQgXHVjODE1XHVkNTc0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjZDFkICROJFx1YWMxY1x1Yzc1OCBcdWFkMTFcdWFjZTAgXHVjNjk0XHVjY2FkXHVjNzc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIzMDBcdWFlMzBcdWM1ZjRcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNzQwIFx1YjJlNFx1Yzc0YyBcdWFjZmNcdWM4MTVcdWM3NDQgXHViYzE4XHViY2Y1XHVkNTU4XHVjNWVjIFx1YmFhOFx1YjRlMCBcdWM2OTRcdWNjYWRcdWM3NDQgXHVjMThjXHVkNjU0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1ZDYwNFx1YzdhYyBcdWIzMDBcdWFlMzBcdWM1ZjRcdWM3NTggXHVjNTVlXHVjYWJkXHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YjMwMCAzXHVhYzFjXHVjNzU4IFx1YWQxMVx1YWNlMCBcdWM2OTRcdWNjYWRcdWM3NDQgXHVkNjU1XHVjNzc4XHVkNTVjIFx1YjJlNFx1Yzc0YywgXHVhZGY4IFx1YzkxMSAyXHVhYzFjXHVjNzU4IFx1YzY5NFx1Y2NhZFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWM1ZWMgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Y2M5OFx1YjlhY1x1ZDU1OFx1YWNlMCBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWI0NTAgXHVjNjk0XHVjY2FkIFx1YzkxMSBcdWM3OTFcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1YjMwMFx1YWUzMFx1YzVmNFx1YzVkMCBcdWIyZTggXHVkNTU4XHViMDk4XHVjNzU4IFx1YzY5NFx1Y2NhZFx1YjljYyBcdWIwYThcdWM1NDQgXHVjNzg4XHViMmU0XHViYTc0LCBcdWFkZjggXHVjNjk0XHVjY2FkXHVjNzQ0IFx1YjJlOFx1YjNjNSBcdWNjOThcdWI5YWNcdWQ1NThcdWFjZTAgXHVjODFjXHVhYzcwXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGNcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzQwIFx1YWRmOCBcdWM2OTRcdWNjYWRcdWM3NTggXHVhYzEyXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMyZGNcdWMyYTRcdWQxNWNcdWM3NzQgXHViYWE4XHViNGUwIFx1YWQxMVx1YWNlMCBcdWM2OTRcdWNjYWRcdWM3NDQgXHVjYzk4XHViOWFjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDFkIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCAkVCRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDFcXGxlIFRcXGxlIDUwXFwsIDAwMCQpPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDExXHVhY2UwIFx1YzY5NFx1Y2NhZFx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxXFxsZSBOXFxsZSAxXFwsIDAwMFxcLCAwMDAkKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWFkMTFcdWFjZTAgXHVjNjk0XHVjY2FkXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQV8xLEFfMixcXGNkb3RzICxBX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDFcXGxlIEFfaVxcbGUgMTBeOSQpPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCAkTiRcdWM3NTggXHVkNTY5XHVjNzQwICQxXFwsIDAwMFxcLCAwMDAkIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViYWE4XHViNGUwIFx1YWQxMVx1YWNlMCBcdWM2OTRcdWNjYWRcdWM3NDQgXHVjYzk4XHViOWFjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDFkIFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgJFQkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzQwOTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBdXRvbWF0aWMgQWR2ZXJ0aXNlbWVudCBQbGFjZW1lbnQgU3lzdGVtIiwiZGVzY3JpcHRpb24iOiI8cD5Nb2xvY28gaXMgYW4gYWR2ZXJ0aXNlbWVudCB0ZWNobm9sb2d5IGNvbXBhbnkgd2hpY2ggaGVscHMgdmFyaW91cyBjb21wYW5pZXMgYWxsIGFyb3VuZCB0aGUgd29ybGQgaW1wcm92ZSB0aGVpciBvbmxpbmUgYWR2ZXJ0aXNpbmcuIEJ5IHVzaW5nIE1vbG9jbyZyc3F1bztzIHRlY2hub2xvZ3ksIGludGVybmV0IHVzZXJzIGNhbiB2aWV3IG1vcmUgcmVsZXZhbnQgYWRzLCBhbmQgYWR2ZXJ0aXNlcnMgY2FuIHByb21vdGUgdGhlaXIgcHJvZHVjdHMgbW9yZSBlZmZlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+TW9sb2NvJnJzcXVvO3MgYXV0b21hdGljIGFkdmVydGlzZW1lbnQgcGxhY2VtZW50IHN5c3RlbSBncm91cHMgcGVuZGluZyBhZHZlcnRpc2VtZW50IHJlcXVlc3RzIGluIHJlYWwtdGltZSB0byBtYXhpbWl6ZSBlZmZpY2llbmN5LiBFYWNoIGFkdmVydGlzZW1lbnQgcmVxdWVzdCBoYXMgYSBwb3NpdGl2ZSBudW1iZXIgYXNzb2NpYXRlZCB0byBpdCwgZGVub3RpbmcgdGhlIGNvc3QgcmVxdWlyZWQgdG8gcHJvY2VzcyB0aGUgcmVxdWVzdC4gR2l2ZW4gJE4kIHBlbmRpbmcgcmVxdWVzdHMgaW4gcXVldWUsIHRoZSBzeXN0ZW0gcHJvY2Vzc2VzIGFsbCByZXF1ZXN0cyBieSByZXBlYXRpbmcgdGhlIGZvbGxvd2luZyBwcm9jZWR1cmUuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q2hlY2sgdXAgdG8gMyByZXF1ZXN0cyBmcm9tIHRoZSBmcm9udCBvZiB0aGUgY3VycmVudGx5IHBlbmRpbmcgcXVldWUuIFNlbGVjdCAyIG9mIHRoZW0sIGFuZCBwcm9jZXNzIHRoZW0gdG9nZXRoZXIsIGFuZCB0aGVuIHJlbW92ZSB0aGVtIGJvdGggZnJvbSB0aGUgcXVldWUuIFRoZSBjb3N0IHRvIGJlIHBhaWQgaXMgdGhlIG1heGltdW0gb2YgdGhlIGNvc3RzIHJlcXVpcmVkIHRvIHByb2Nlc3MgZWFjaCBvZiB0aGUgdHdvIHJlcXVlc3RzLjxcL2xpPlxyXG5cdDxsaT5JZiB0aGVyZSBpcyBvbmx5IG9uZSByZXF1ZXN0IGluIHRoZSBjdXJyZW50bHkgcGVuZGluZyBxdWV1ZSwgcHJvY2VzcyBhbmQgcmVtb3ZlIGl0IGZyb20gdGhlIHF1ZXVlLiBJbiB0aGlzIGNhc2UsIHRoZSBjb3N0IGlzIHRoZSBjb3N0IHJlcXVpcmVkIHRvIHByb2Nlc3MgdGhlIHJlcXVlc3QuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RmluZCB0aGUgbWluaW11bSB0b3RhbCBjb3N0IHJlcXVpcmVkIGZvciB0aGUgc3lzdGVtIHRvIHByb2Nlc3MgYWxsIGFkdmVydGlzZW1lbnQgcmVxdWVzdHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyAkVCQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLiAoJDFcXGxlIFRcXGxlIDUwXFwsIDAwMCQpPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGZvciBlYWNoIHRlc3RjYXNlIGNvbnRhaW5zICROJCwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBhZHZlcnRpc2VtZW50IHJlcXVlc3RzLiAoJDFcXGxlIE5cXGxlIDFcXCwgMDAwXFwsIDAwMCQpPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyAkTiQgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRBXzEsQV8yLFxcY2RvdHMgLEFfTiQsIGRlbm90aW5nIHRoZSBjb3N0IHJlcXVpcmVkIHRvIHByb2Nlc3MgZWFjaCByZXF1ZXN0LiAoJDFcXGxlIEFfaVxcbGUgMTBeOSQpPFwvcD5cclxuXHJcbjxwPlRoZSBzdW0gb2YgJE4kIG92ZXIgYWxsIHRlc3RjYXNlcyBkb2VzIG5vdCBleGNlZWQgJDFcXCwgMDAwXFwsIDAwMCQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdGNhc2UsIHByaW50IHRoZSBtaW5pbXVtIHRvdGFsIGNvc3QgaW4gYSBzaW5nbGUgbGluZS48XC9wPlxyXG5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==