다다스는 수직선 위에서 농사를 짓고 있다. 처음부터 개의 씨앗이 심어져 있으며, 번 씨앗은 좌표 에 있다. 모든 씨앗의 위치는 서로 다르다.
번 씨앗의 가치는 이다. 번 씨앗은 일째에만 수확할 수 있다.
다다스는 처음 위치를 수직선 위의 원하는 곳으로 정할 수 있다. 어떤 날에 씨앗을 수확하지 않아도 된다. 일째에 번 씨앗을 수확하려면 현재 위치에서 까지 이동해야 한다.
이동하는 동안 현재 위치와 사이에 아직 수확되지 않은 씨앗이 있다면 그 씨앗을 밟게 된다. 밟힌 씨앗은 이후 수확할 수 없다. 수확하려는 번 씨앗 자체는 밟힌 것으로 처리하지 않는다.
수확할 씨앗들을 적절히 정하여 얻는 가치의 합을 최대화하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 얻을 수 있는 가치의 합의 최댓값을 한 줄에 출력한다.
각 케이스는 다음과 같은 형식으로 주어진다.
| 3 | 52 | 추가적인 제약이 없다. |
