시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1536 MB303786428.444%

문제

준겸이는 $2^0$명은 금상, $2^1$명은 은상, $2^2$명은 동상으로 총 7명에게 상금을 주는 Bye, Bye 2021 대회를 열었다. 준겸이에게는 $N$개의 상품권이 있으며, 상품권 $i (1 ≤ i ≤ N)$는 $A_i$ 원으로 교환될 수 있다. 수상자에게는 상금으로 각각 하나의 상품권만 지급하려고 한다. 준겸이는 상금이 불균형해질 것을 우려해 아래와 같은 조건을 만족하는 상금 구성을 찾으려고 한다.

순서대로 1등에게 지급할 상금을 $P_1$, 2등을 $P_2$, 3등을 $P_3$, ..., 7등을 $P_7$ 라고 하자.

  • $P_1 \ge P_2 \ge P_3 \ge P_4 \ge P_5 \ge P_6 \ge P_7$
  • $P_1 < P_2 + P_3 < P_4 + P_5 + P_6 + P_7$

준겸이가 가지고 있는 $N$개의 상품권이 주어졌을 때, 이런 조건을 만족하는 상금 분배가 가능한 지 알려주는 프로그램을 작성해보자. 만약, 조건을 만족하는 상금 분배가 불가능하다면 -1을, 그렇지 않다면 가능한 모든 경우의 상금의 총합 중에서 최댓값을 출력해야 한다.

입력

첫째 줄에 $N(7 \le N \le 500\,000)$이 주어진다.

둘째 줄에는 $N$개의 정수 $A_i (1 \le A_i \le 2 \times 10^8)$가 공백으로 구분되어 주어진다.

출력

조건을 만족하는 상금 분배가 불가능하다면 -1을, 그렇지 않다면 가능한 모든 경우의 상금의 총합 중에서 최댓값을 출력하라.

예제 입력 1

7
1 2 3 4 5 6 7

예제 출력 1

-1

예제 입력 2

8
1 2 3 4 5 6 7 8

예제 출력 2

35

예제 입력 3

10
5 5 5 5 5 5 10 5 5 5

예제 출력 3

35
W3sicHJvYmxlbV9pZCI6IjIwNTMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGMxXHVhZTA4IFx1YmQ4NFx1YmMzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjOTAwXHVhY2I4XHVjNzc0XHViMjk0ICQyXjAkXHViYTg1XHVjNzQwIFx1YWUwOFx1YzBjMSwgJDJeMSRcdWJhODVcdWM3NDAgXHVjNzQwXHVjMGMxLCAkMl4yJFx1YmE4NVx1Yzc0MCBcdWIzZDlcdWMwYzFcdWM3M2NcdWI4NWMgXHVjZDFkIDdcdWJhODVcdWM1ZDBcdWFjOGMgXHVjMGMxXHVhZTA4XHVjNzQ0IFx1YzhmY1x1YjI5NCA8Y29kZT5CeWUsIEJ5ZSAyMDIxPFwvY29kZT4mbmJzcDtcdWIzMDBcdWQ2OGNcdWI5N2MgXHVjNWY0XHVjNWM4XHViMmU0LiBcdWM5MDBcdWFjYjhcdWM3NzRcdWM1ZDBcdWFjOGNcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YzBjMVx1ZDQ4OFx1YWQ4Y1x1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzBjMVx1ZDQ4OFx1YWQ4YyAkaSZuYnNwOygxICZsZTsgaSAmbGU7IE4pJFx1YjI5NCAkQV9pJCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVhZDUwXHVkNjU4XHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YzBjMVx1Yzc5MFx1YzVkMFx1YWM4Y1x1YjI5NCBcdWMwYzFcdWFlMDhcdWM3M2NcdWI4NWMgXHVhYzAxXHVhYzAxIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMwYzFcdWQ0ODhcdWFkOGNcdWI5Y2MgXHVjOWMwXHVhZTA5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTAwXHVhY2I4XHVjNzc0XHViMjk0IFx1YzBjMVx1YWUwOFx1Yzc3NCBcdWJkODhcdWFkZTBcdWQ2MTVcdWQ1NzRcdWM5YzggXHVhYzgzXHVjNzQ0IFx1YzZiMFx1YjgyNFx1ZDU3NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMGMxXHVhZTA4IFx1YWQ2Y1x1YzEzMVx1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgMVx1YjRmMVx1YzVkMFx1YWM4YyBcdWM5YzBcdWFlMDlcdWQ1NjAmbmJzcDtcdWMwYzFcdWFlMDhcdWM3NDQgJFBfMSQsIDJcdWI0ZjFcdWM3NDQgJFBfMiQsIDNcdWI0ZjFcdWM3NDQgJFBfMyQsIC4uLiwgN1x1YjRmMVx1Yzc0NCAkUF83JCBcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRQXzEgXFxnZSZuYnNwO1BfMiBcXGdlJm5ic3A7UF8zJm5ic3A7XFxnZSBQXzQmbmJzcDtcXGdlIFBfNSZuYnNwO1xcZ2UgUF82Jm5ic3A7XFxnZSBQXzckPFwvbGk+XHJcblx0PGxpPiRQXzEmbmJzcDsmbHQ7IFBfMiZuYnNwOysgUF8zJm5ic3A7Jmx0OyBQXzQmbmJzcDsrIFBfNSZuYnNwOysgUF82Jm5ic3A7KyBQXzckPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjOTAwXHVhY2I4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YzBjMVx1ZDQ4OFx1YWQ4Y1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI3ZjAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMwYzFcdWFlMDggXHViZDg0XHViYzMwXHVhYzAwJm5ic3A7XHVhYzAwXHViMmE1XHVkNTVjJm5ic3A7XHVjOWMwIFx1YzU0Y1x1YjgyNFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWI5Y2NcdWM1N2QsIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMGMxXHVhZTA4IFx1YmQ4NFx1YmMzMFx1YWMwMCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgPGNvZGU+LTE8XC9jb2RlPlx1Yzc0NCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCZuYnNwO1x1YWMwMFx1YjJhNVx1ZDU1YyZuYnNwO1x1YmFhOFx1YjRlMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMGMxXHVhZTA4XHVjNzU4IFx1Y2QxZFx1ZDU2OSBcdWM5MTFcdWM1ZDBcdWMxMWMgPHN0cm9uZz5cdWNkNWNcdWIzMTNcdWFjMTI8XC9zdHJvbmc+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwICROKDcgXFxsZSZuYnNwO04gXFxsZSZuYnNwOzUwMFxcLDAwMCkkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRBX2kgKDEgXFxsZSZuYnNwO0FfaSBcXGxlJm5ic3A7MiBcXHRpbWVzJm5ic3A7MTBeOCkkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMGMxXHVhZTA4IFx1YmQ4NFx1YmMzMFx1YWMwMCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgPGNvZGU+LTE8XC9jb2RlPlx1Yzc0NCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCZuYnNwO1x1YWMwMFx1YjJhNVx1ZDU1YyZuYnNwO1x1YmFhOFx1YjRlMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMGMxXHVhZTA4XHVjNzU4IFx1Y2QxZFx1ZDU2OSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDUzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikp1bmt5ZW9tJ3MgQ29udGVzdCIsImRlc2NyaXB0aW9uIjoiPHA+SnVua3llb20gYW5kIGhpcyBmcmllbmRzIE15dW5nIGFuZCBNeWVvbmcgYXJlIHBsYW5uaW5nIHRvIGhvbGQgYSBwcm9ncmFtbWluZyBjb250ZXN0IHdpdGggb25lIGdvbGQgKGZpcnN0IHBsYWNlKSwgdHdvIHNpbHZlciAocGxhY2VzIDIgYW5kIDMpLCBhbmQgZm91ciBicm9uemUgbWVkYWxzIChwbGFjZXMgNCwgNSwgNiwgNykuPFwvcD5cclxuXHJcbjxwPlRoZSBzcG9uc29ycyBnYXZlICROJCBnaWZ0IGNhcmRzIGZvciB0aGUgY29udGVzdCwgJGkkLXRoIG9mIHRoZW0gY29zdHMgJEFfaSQuIEVhY2ggbWVkYWxpc3Qgc2hhbGwgYmUgYXdhcmRlZCBleGFjdGx5IG9uZSBjYXJkLiBMZXQgJFBfaSQgYmUgdGhlIHByaXplIGZvciB0aGUgY2FyZCBhd2FyZGVkIHRvIHRoZSBjb250ZXN0YW50IHRha2luZyAkaSQtdGggcGxhY2UuIFRoZSBkaXN0cmlidXRpb24gaXMgY29uc2lkZXJlZCA8ZW0+ZmFpcjxcL2VtPiBpZiB0aGUgZm9sbG93aW5nIHR3byBpbmVxdWFsaXRpZXMgYXJlIGhlbGQ6PFwvcD5cclxuXHJcbjxwPiQkIFBfMSBcXGdlIFBfMiBcXGdlIFBfMyBcXGdlIFBfNCBcXGdlIFBfNSBcXGdlIFBfNiBcXGdlIFBfNyAkJDxcL3A+XHJcblxyXG48cD5hbmQmbmJzcDs8XC9wPlxyXG5cclxuPHA+JCQgUF8xICZsdDsgUF8yICsgUF8zICZsdDsgUF80ICsgUF81ICsgUF82ICsgUF83XFx0ZXh0ey59ICQkPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSB2YWx1ZXMgJEFfaSQsIGZpbmQgb3V0IGlmIGEgZmFpciBkaXN0cmlidXRpb24gb2YgcHJpemVzIGV4aXN0cy4gSWYgaXQgZG9lcywgcHJpbnQgdGhlIG1heGltdW0gcG9zc2libGUgc3VtIG9mICRQX2kkIGZvciBhIGZhaXIgZGlzdHJpYnV0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgJE4kLCB0aGUgbnVtYmVyIG9mIGdpZnQgY2FyZHMgKCQ3IFxcbGUgTiBcXGxlIDUgXFxjZG90IDEwXjUkKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBpbnRlZ2VycyAkQV9pJDogdGhlIHByaXplcyBmb3IgdGhlIGNhcmRzICgkMSBcXGxlIEFfaSBcXGxlIDIgXFxjZG90IDEwXjgkKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiBhIGZhaXIgZGlzdHJpYnV0aW9uIG9mIHByaXplcyBpcyBpbXBvc3NpYmxlLCBwcmludCAkLTEkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PdGhlcndpc2UgcHJpbnQgb25lIGludGVnZXI6IHRoZSBtYXhpbXVtIHBvc3NpYmxlIHRvdGFsIHByaXplIG9mIHRoZSBmYWlybHkgZGlzdHJpYnV0ZWQgZ2lmdCBjYXJkcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d