개의 건물을 설계하려고 한다. 번 건물은 최대 층까지 지을 수 있다.
건물의 높이가 층이면 도시의 완성도가 만큼 증가한다. 도시의 완성도의 초깃값은 이며, 각 건물의 높이는 이상의 정수여야 한다.
도시의 완성도의 최댓값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트케이스마다 도시의 완성도의 최댓값을 한 줄에 출력한다.
첫 번째 테스트케이스에서는 각 건물을 차례로 층으로 지으면 된다. 각 건물의 기여는 이므로 완성도는 이며, 이것이 최댓값이다.
는 테스트케이스의 수이며, 각 테스트케이스는 다음과 같은 형식으로 주어진다.
여기서 이다.
| 2 | 68 | 추가적인 제약이 없다. |
두 번째 테스트케이스에서는 각 건물을 차례로 층으로 지으면 된다. 세 건물 모두 만큼 기여하므로 완성도는 이며, 이것이 최댓값이다.
