Statement
지문 언어
다다스는 수직선 위에서 농사를 짓고 있다. 처음부터 개의 씨앗이 심어져 있으며, 번 씨앗은 좌표 에 있다. 모든 씨앗의 위치는 서로 다르다.
번 씨앗의 가치는 이다. 번 씨앗은 일째에만 수확할 수 있다.
다다스는 처음 위치를 수직선 위의 원하는 곳으로 정할 수 있다. 어떤 날에 씨앗을 수확하지 않아도 된다. 일째에 번 씨앗을 수확하려면 현재 위치에서 까지 이동해야 한다.
이동하는 동안 현재 위치와 사이에 아직 수확되지 않은 씨앗이 있다면 그 씨앗을 밟게 된다. 밟힌 씨앗은 이후 수확할 수 없다. 수확하려는 번 씨앗 자체는 밟힌 것으로 처리하지 않는다.
수확할 씨앗들을 적절히 정하여 얻는 가치의 합을 최대화하여라.
Input
입력은 다음과 같은 형식으로 주어진다.
각 케이스는 다음과 같은 형식으로 주어진다.
Output
각 테스트 케이스마다 얻을 수 있는 가치의 합의 최댓값을 한 줄에 출력한다.
Constraints
- .
- .
- ().
- ().
- ().
- 모든 테스트 케이스에 대한 의 합은 이하이다.
Subtasks
Samples
입력
3
3
2 5
1 4
3 6
4
2 10
4 20
1 30
3 40
5
5 3
1 100
4 4
2 90
3 5
출력
15
80
195