시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB188423128.182%

문제

N(3 ≤ N ≤ 40)개의 막대기들이 있다. 각각의 막대기들은 길이가 서로 같은 수도 있고, 서로 다를 수도 있다. 이러한 막대기들을 연결하여 하나의 삼각형을 만들려고 한다. 이때 사용하지 않는 막대기가 있어서는 안 된다. 즉, 각 막대기들을 적당히 세 그룹으로 나눈 다음, 각 그룹에 있는 막대기들을 일렬로 연결하고, 이를 이용하여 삼각형을 만드는 것이다.

이와 같이 삼각형을 만들었을 때, 가장 큰 삼각형의 넓이를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 막대기의 길이 L(1 ≤ L ≤ 40)이 주어진다.

출력

첫째 줄에 최대 면적을 100배한 값을 소수점 아래에서 버림한 정수를 출력한다. 만약 삼각형을 만들 수 없다면 -1을 출력한다.

예제 입력 1

5
1
1
3
3
4

예제 출력 1

692

힌트

삼각형의 세 변의 길이가 a, b, c일 때, s=(a+b+c)/2 로 두면, 넓이의 제곱은 s×(s-a)×(s-b)×(s-c)이 된다.

W3sicHJvYmxlbV9pZCI6IjIyNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWQ2MTUgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5OKDMgJmxlOyBOICZsZTsgNDApXHVhYzFjXHVjNzU4IFx1YjljOVx1YjMwMFx1YWUzMFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWI5YzlcdWIzMDBcdWFlMzBcdWI0ZTRcdWM3NDAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWFjMTlcdWM3NDAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCwgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YzVlYyBcdWQ1NThcdWIwOThcdWM3NTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YjljOVx1YjMwMFx1YWUzMFx1YWMwMCBcdWM3ODhcdWM1YjRcdWMxMWNcdWIyOTQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWFjMDEgXHViOWM5XHViMzAwXHVhZTMwXHViNGU0XHVjNzQ0IFx1YzgwMVx1YjJmOVx1ZDc4OCBcdWMxMzggXHVhZGY4XHViOGY5XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIyZTRcdWM3NGMsIFx1YWMwMSBcdWFkZjhcdWI4ZjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjljOVx1YjMwMFx1YWUzMFx1YjRlNFx1Yzc0NCBcdWM3N2NcdWI4MmNcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHVhY2UwLCBcdWM3NzRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTc0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWI5YzlcdWIzMDBcdWFlMzBcdWM3NTggXHVhZTM4XHVjNzc0IEwoMSAmbGU7IEwgJmxlOyA0MClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIFx1YmE3NFx1YzgwMVx1Yzc0NCAxMDBcdWJjMzBcdWQ1NWMgXHVhYzEyXHVjNzQ0IFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM1NDRcdWI3OThcdWM1ZDBcdWMxMWMgXHViYzg0XHViOWJjXHVkNTVjIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjMTM4IFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgYSwgYiwgY1x1Yzc3YyBcdWI1NGMsIHM9KGErYitjKVwvMiBcdWI4NWMgXHViNDUwXHViYTc0LCBcdWIxMTNcdWM3NzRcdWM3NTggXHVjODFjXHVhY2YxXHVjNzQwIHMmdGltZXM7KHMtYSkmdGltZXM7KHMtYikmdGltZXM7KHMtYylcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjI0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyaWFuZ3VsYXIgUGFzdHVyZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkxpa2UgZXZlcnlvbmUsIGNvd3MgZW5qb3kgdmFyaWV0eS4gVGhlaXIgY3VycmVudCBmYW5jeSBpcyBuZXcgc2hhcGVzIGZvciBwYXN0dXJlcy4gVGhlIG9sZCByZWN0YW5ndWxhciBzaGFwZXMgYXJlIG91dCBvZiBmYXZvcjsgbmV3IGdlb21ldHJpZXMgYXJlIHRoZSBmYXZvcml0ZS48XC9wPlxyXG5cclxuPHA+SS4gTS4gSGVpLCB0aGUgbGVhZCBjb3cgcGFzdHVyZSBhcmNoaXRlY3QsIGlzIGluIGNoYXJnZSBvZiBjcmVhdGluZyBhIHRyaWFuZ3VsYXIgcGFzdHVyZSBzdXJyb3VuZGVkIGJ5IG5pY2Ugd2hpdGUgZmVuY2UgcmFpbHMuIFNoZSBpcyBzdXBwbGllZCB3aXRoIE4gKDMgJmx0Oz0gTiAmbHQ7PSA0MCkgZmVuY2Ugc2VnbWVudHMgKGVhY2ggb2YgaW50ZWdlciBsZW5ndGggTGkgKDEgJmx0Oz0gTGkgJmx0Oz0gNDApIGFuZCBtdXN0IGFycmFuZ2UgdGhlbSBpbnRvIGEgdHJpYW5ndWxhciBwYXN0dXJlIHdpdGggdGhlIGxhcmdlc3QgZ3JhemluZyBhcmVhLiBNcy4gSGVpIG11c3QgdXNlIGFsbCB0aGUgcmFpbHMgdG8gY3JlYXRlIHRocmVlIHNpZGVzIG9mIG5vbi16ZXJvIGxlbmd0aC48XC9wPlxyXG5cclxuPHA+SGVscCBNcy4gSGVpIGNvbnZpbmNlIHRoZSByZXN0IG9mIHRoZSBoZXJkIHRoYXQgcGxlbnR5IG9mIGdyYXppbmcgbGFuZCB3aWxsIGJlIGF2YWlsYWJsZS5DYWxjdWxhdGUgdGhlIGxhcmdlc3QgYXJlYSB0aGF0IG1heSBiZSBlbmNsb3NlZCB3aXRoIGEgc3VwcGxpZWQgc2V0IG9mIGZlbmNlIHNlZ21lbnRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgTjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IE4gbGluZXMsIGVhY2ggd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIHJlcHJlc2VudGluZyBvbmUgZmVuY2Ugc2VnbWVudCYjMzk7cyBsZW5ndGguIFRoZSBsZW5ndGhzIGFyZSBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+QSBzaW5nbGUgbGluZSB3aXRoIHRoZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIHRydW5jYXRlZCBpbnRlZ2VyIHJlcHJlc2VudGF0aW9uIG9mIHRoZSBsYXJnZXN0IHBvc3NpYmxlIGVuY2xvc2VkIGFyZWEgbXVsdGlwbGllZCBieSAxMDAuIE91dHB1dCAtMSBpZiBubyB0cmlhbmdsZSBvZiBwb3NpdGl2ZSBhcmVhIG1heSBiZSBjb25zdHJ1Y3RlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d