시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 422 120 70 25.735%

문제

NSA는 점점 늘어나는 러시아어와 스페인어 번역 데이터와 전화 도청 파일의 용량 때문에, 데이터 센터의 용량을 최대 1 엑사바이트로 확장하려고 한다. 

NSA의 예산은 넉넉한 편이 아니기 때문에, 새 디스크를 구매할 수 없다. 따라서, 불필요한 데이터를 제거해 용량을 확보하려고 한다.

모든 서버는 네 디스크가 RAID-1을 이루고 있다. RAID-5로 방식을 바꿔 용량을 확보해보자.

현재 데이터 센터에는 총 n개의 RAID-1 세트가 있다. 각각의 세트 i는 크기가 Si인 디스크로 이루어져 있다. 이 세트는 데이터 Si GB를 보관할 수 있다. RAID-5 세트로 변환하면 보관할 수 있는 용량이 총 세 배가 된다. (3 · Si GB) 되도록 적은 용량을 RAID-5로 변환해 필요한 용량을 얻는 프로그램을 작성하시오.

디스크의 용량 S = 4이고, 저장 가능 용량은 4 GB (D0 ... D3)과 3 · 4 = 12 GB (D0 ... D11) 이다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 RAID-1 세트의 수 n과 확보해야 하는 용량 e 가 주어진다. (1 ≤ n ≤ 100 and 0 ≤ e ≤ 109)

둘째 줄에는 각 세트의 크기 S1 ... Sn (1 ≤ Si ≤ 2 000)가 주어진다.

출력

각 테스트 케이스 마다 변환해야 하는 용량(GB)을 출력한다. 용량을 e만큼 더 확보할 수 없는 경우에는 “FULL”을 출력한다.

예제 입력 1

3
2 500
500 500
4 2400
400 600 700 1000
2 1000
10 10

예제 출력 1

500
1300
FULL

힌트

  • 첫 번째 예제의 경우에, RAID 세트 하나를 변환하면 된다. 새로운 용량은 1500 + 500 = 2000 GB가 된다.
  • 두 번째 예제는 600 GB와 700 GB 디스크를 변환하면 400 + 600 + 700 + 1000 = 2700 GB, 400 + 1800 + 2100 + 1000 = 5300 GB가 된다. 다른 변환은 모두 비효율적이다.
  • 세 번째 예제의 경우는 필요한 용량을 확보할 수 없다.
W3sicHJvYmxlbV9pZCI6IjkzMjciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YTlcdWI3YzkgXHVkNjU1XHViY2Y0IiwiZGVzY3JpcHRpb24iOiI8cD5OU0FcdWIyOTQgXHVjODEwXHVjODEwIFx1YjI5OFx1YzViNFx1YjA5OFx1YjI5NCBcdWI3ZWNcdWMyZGNcdWM1NDRcdWM1YjRcdWM2NDAgXHVjMmE0XHVkMzk4XHVjNzc4XHVjNWI0IFx1YmM4OFx1YzVlZCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM2NDAgXHVjODA0XHVkNjU0IFx1YjNjNFx1Y2NhZCBcdWQzMGNcdWM3N2NcdWM3NTggXHVjNmE5XHViN2M5IFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzY1x1ZDEzMFx1Yzc1OCBcdWM2YTlcdWI3YzlcdWM3NDQgXHVjZDVjXHViMzAwIDEgXHVjNWQxXHVjMGFjXHViYzE0XHVjNzc0XHVkMmI4XHViODVjIFx1ZDY1NVx1YzdhNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5TQVx1Yzc1OCBcdWM2MDhcdWMwYjBcdWM3NDAgXHViMTA5XHViMTA5XHVkNTVjIFx1ZDNiOFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMwYzggXHViNTE0XHVjMmE0XHVkMDZjXHViOTdjIFx1YWQ2Y1x1YjllNFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YmQ4OFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIzNzBcdWM3NzRcdWQxMzBcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTc0IFx1YzZhOVx1YjdjOVx1Yzc0NCBcdWQ2NTVcdWJjZjRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjMTFjXHViYzg0XHViMjk0IFx1YjEyNCBcdWI1MTRcdWMyYTRcdWQwNmNcdWFjMDAgUkFJRC0xXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyZTQuIFJBSUQtNVx1Yjg1YyBcdWJjMjlcdWMyZGRcdWM3NDQgXHViYzE0XHVhZmQ0IFx1YzZhOVx1YjdjOVx1Yzc0NCBcdWQ2NTVcdWJjZjRcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTNjXHVkMTMwXHVjNWQwXHViMjk0IFx1Y2QxZCBuXHVhYzFjXHVjNzU4IFJBSUQtMSBcdWMxMzhcdWQyYjhcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMTM4XHVkMmI4IGlcdWIyOTQgXHVkMDZjXHVhZTMwXHVhYzAwIFM8c3ViPmk8XC9zdWI+XHVjNzc4IFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjMTM4XHVkMmI4XHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMCBTPHN1Yj5pPFwvc3ViPiBHQlx1Yjk3YyBcdWJjZjRcdWFkMDBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gUkFJRC01IFx1YzEzOFx1ZDJiOFx1Yjg1YyBcdWJjYzBcdWQ2NThcdWQ1NThcdWJhNzQgXHViY2Y0XHVhZDAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNmE5XHViN2M5XHVjNzc0IFx1Y2QxZCBcdWMxMzggXHViYzMwXHVhYzAwIFx1YjQxY1x1YjJlNC4gKDMgJm1pZGRvdDsgUzxzdWI+aTxcL3N1Yj4gR0IpIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM4MDFcdWM3NDAgXHVjNmE5XHViN2M5XHVjNzQ0IFJBSUQtNVx1Yjg1YyBcdWJjYzBcdWQ2NThcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzZhOVx1YjdjOVx1Yzc0NCBcdWM1YmJcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9yYWlkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExMXB4OyBsaW5lLWhlaWdodDoxLjZlbTsgd2lkdGg6NDYzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViNTE0XHVjMmE0XHVkMDZjXHVjNzU4IFx1YzZhOVx1YjdjOSBTID0gNFx1Yzc3NFx1YWNlMCwgXHVjODAwXHVjN2E1IFx1YWMwMFx1YjJhNSBcdWM2YTlcdWI3YzlcdWM3NDAgNCBHQiAoRDAgLi4uIEQzKVx1YWNmYyAzICZtaWRkb3Q7IDQgPSAxMiBHQiAoRDAgLi4uIEQxMSkgXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHViMjk0IDEwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFJBSUQtMSBcdWMxMzhcdWQyYjhcdWM3NTggXHVjMjE4IG5cdWFjZmMgXHVkNjU1XHViY2Y0XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM2YTlcdWI3YzkgZSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygxICZsZTsgbiAmbGU7IDEwMCBhbmQgMCAmbGU7IGUgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzEzOFx1ZDJiOFx1Yzc1OCBcdWQwNmNcdWFlMzAmbmJzcDtTPHN1Yj4xPFwvc3ViPiZuYnNwOy4uLiBTPHN1Yj5uPFwvc3ViPiZuYnNwOygxICZsZTsgUzxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDIgMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1YmNjMFx1ZDY1OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNmE5XHViN2M5KEdCKVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzZhOVx1YjdjOVx1Yzc0NCBlXHViOWNjXHVkMDdjIFx1YjM1NCBcdWQ2NTVcdWJjZjRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJmxkcXVvOzxjb2RlPkZVTEw8XC9jb2RlPiZyZHF1bztcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8dWw+XHJcblx0PGxpPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCwgUkFJRCBcdWMxMzhcdWQyYjggXHVkNTU4XHViMDk4XHViOTdjIFx1YmNjMFx1ZDY1OFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM2YTlcdWI3YzlcdWM3NDAgMTUwMCArIDUwMCA9IDIwMDAgR0JcdWFjMDAgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1YjI5NCA2MDAgR0JcdWM2NDAgNzAwIEdCIFx1YjUxNFx1YzJhNFx1ZDA2Y1x1Yjk3YyBcdWJjYzBcdWQ2NThcdWQ1NThcdWJhNzQmbmJzcDs0MDAgKyA2MDAgKyA3MDAgKyAxMDAwID0gMjcwMCBHQiwgNDAwICsgMTgwMCArIDIxMDAgKyAxMDAwID0gNTMwMCBHQlx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YjJlNFx1Yjk3OCBcdWJjYzBcdWQ2NThcdWM3NDAgXHViYWE4XHViNDUwIFx1YmU0NFx1ZDZhOFx1YzcyOFx1YzgwMVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHViMjk0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM2YTlcdWI3YzlcdWM3NDQgXHVkNjU1XHViY2Y0XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzMjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKdXN0IEVub3VnaCBTcGFjZSIsImRlc2NyaXB0aW9uIjoiPHA+QWZ0ZXIgYSBQUiBtaXNoYXAgd2l0aCBhIGZvcm1lciBlbXBsb3llZSwgdGhlIE5TQSBtaWdodCBuZWVkIHRvIGluY3JlYXNlIHN0b3JhZ2UgaW4gb25lIG9mIHRoZWlyIGRhdGFjZW50ZXJzOiB0aGUgUnVzc2lhbiBhbmQgU3BhbmlzaCB0cmFuc2xhdG9ycyBoYXZlIGEgYmFja2xvZywgYW5kIHRoZSBjYXB0dXJlZCBwaG9uZSBjb252ZXJzYXRpb25zIG5lZWQgdG8gYmUgc3RvcmVkIGluIHRoZSBtZWFudGltZS4gVXAgdG8gMSBleGFieXRlIG9mIGRhdGEgbmVlZHMgdG8gYmUgc3RvcmVkLiBVbmZvcnR1bmF0ZWx5LCB0aGVyZSBpcyBjdXJyZW50bHkgbm8gZXh0cmEgc3RvcmFnZSBhdmFpbGFibGUgYXQgYWxsLjxcL3A+XHJcblxyXG48cD5EdWUgdG8gYnVkZ2V0IGxpbWl0YXRpb25zLCBpdCBpcyBub3QgcG9zc2libGUgdG8gaW1tZWRpYXRlbHkgYnV5IG5ldyBkaXNrcywgYW5kIHRoZSBzeXN0ZW0gYWRtaW5pc3RyYXRvciAoeW91KSB3YW50cyB0byBzb2x2ZSB0aGlzIGJ5IHJlZHVjaW5nIHRoZSBkYXRhIHJlZHVuZGFuY3kuIEZvciBwZXJmb3JtYW5jZSBhbmQgcmVsaWFiaWxpdHksIGFsbCBkYXRhIGlzIGN1cnJlbnRseSBvbiBsYXJnZSBSQUlELTEgc2V0cyBvZiBmb3VyIGRpc2tzIGluIGVhY2ggc2VydmVyLiBNb3JlIGRhdGEgY2FuIGJlIHN0b3JlZCBieSBjb252ZXJ0aW5nIHNvbWUgb2YgdGhlc2Ugc2V0cyB0byB0aGUgc2xvd2VyIFJBSUQtNSB0ZWNobmlxdWUuPFwvcD5cclxuXHJcbjxwPlNwZWNpXHVmYjAxY2FsbHksIHRoZXJlIGFyZSBjdXJyZW50bHkgbiBSQUlELTEgc2V0cy4gRWFjaCBzZXQgaSBpcyBidWlsdCB1c2luZyBkaXNrcyBvZiBzaXplIFM8c3ViPmk8XC9zdWI+LCBhbmQgdGhpcyBzZXQgY2FuIGhvbGQgUzxzdWI+aTxcL3N1Yj4gR0Igb2YgZGF0YS4gSWYgeW91IGNvbnZlcnQgb25lIHNldCB0byBSQUlELTUsIGl0IGNhbiBob2xkIHRocmVlIHRpbWVzIGFzIG11Y2ggZGF0YTogMyAmbWlkZG90OyBTPHN1Yj5pPFwvc3ViPiBHQi4gWW91IHdhbnQgdG8gY29udmVydCBhcyBmZXcgR0JzIG9mIHN0b3JhZ2UgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcmFpZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTFweDsgd2lkdGg6NDYzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RGlza3Mgd2l0aCBzaXplIFMgPSA0LCBjYXBhY2l0eSByZXNwZWN0aXZlbHkgNCBHQiAoRDAgLi4uIEQzKSBhbmQgMyZuYnNwOyZtaWRkb3Q7Jm5ic3A7NCA9IDEyIEdCIChEMCAuLi4gRDExKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIG4gYW5kIGUgKDEgJmxlOyBuICZsZTsgMTAwIGFuZCAwICZsZTsgZSAmbGU7IDEwPHN1cD45PFwvc3VwPik6IHRoZSBudW1iZXIgb2YgUkFJRC0xIHNldHMsIGFuZCB0aGUgYW1vdW50IG9mIGV4dHJhIHNwYWNlIGluIEdCIHJlcXVpcmVkLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggbiBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgUzxzdWI+MTxcL3N1Yj4gLi4uIFM8c3ViPm48XC9zdWI+ICgxICZsZTsgUzxzdWI+aTxcL3N1Yj4gJmxlOyAyIDAwMCk6IHRoZSBzaXplcyBvZiBhbGwgcmFpZCBzZXRzIGluIEdCLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSBudW1iZXIgb2YgR0IgeW91IG5lZWQgdG8gY29udmVydCwgb3IgdGhlIHN0cmluZyAmbGRxdW87PGNvZGU+RlVMTDxcL2NvZGU+JnJkcXVvOyBpZiBub3QgZW5vdWdoIGRpc2tzcGFjZSBjYW4gYmUgZnJlZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHVsPlxyXG5cdDxsaT5JbiB0aGUgXHVmYjAxcnN0IGV4YW1wbGUsIGl0IGlzIGVub3VnaCB0byBjb252ZXJ0IG9uZSBSQUlELXNldDogdGhlIG5ldyBjYXBhY2l0eSBpcyB0aGVuIDE1MDAgKyA1MDAgPSAyMDAwIEdCLjxcL2xpPlxyXG5cdDxsaT5JbiB0aGUgc2Vjb25kIGV4YW1wbGUsIGNvbnZlcnRpbmcgdGhlIDYwMCBHQiBhbmQgNzAwIEdCIGRpc2tzIHdpbGwgaW5jcmVhc2UgdGhlIHN0b3JhZ2UgZnJvbSA0MDAgKyA2MDAgKyA3MDAgKyAxMDAwID0gMjcwMCBHQiB0byA0MDAgKyAxODAwICsgMjEwMCArIDEwMDAgPSA1MzAwIEdCLCBlbm91Z2ggdG8gc3RvcmUgdGhlIGV4dHJhIDI0MDAgR0Igb2YgZGF0YS4gQWxsIG90aGVyIGNvbnZlcnNpb25zIGFyZSBsZXNzIGVmXHVmYjAxY2llbnQuPFwvbGk+XHJcblx0PGxpPkluIHRoZSB0aGlyZCBleGFtcGxlIHRoZXJlIGlzIG5vIHdheSB0byBjb21lIHVwIHdpdGggdGhlIHJlcXVpcmVkIGFtb3VudCBvZiBmcmVlIGRpc2sgc3BhY2UuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==