한국기술교육대학교에 재학 중인 윤철이는 이번 학기에 과탑이 되기 위해 시험 공부를 정말 열심히 했습니다.
그리고 대망의 알고리즘 과목 기말고사 당일. 이 시험만 좋은 점수를 받으면 과탑이 되는 것은 따놓은 당상이었습니다.
윤철이는 떨리는 마음으로 시험지를 받고 시험이 시작됐는데...

'뭐야, 문제가 왜 이리 많아?!'

생전 처음 보는 시험지의 두께와 문제의 양에 윤철이는 소스라치게 놀랐습니다.
이내 진정하고 시험지를 빠르게 훑어본 결과, 3가지 사실을 알게 되었습니다.

1. 문제는 총 N개 있다.
2. 모든 문제는 1초만에 풀 수 있을 정도로 쉽다.
3. 문제마다 풀었을 때 얻을 수 있는 점수가 있다.

현재 남은 시험 시간은 K초. 여유를 부릴 만큼 넉넉하지는 않았습니다.
모든 문제를 풀 수 없을 수도 있어서 윤철이는 남은 시험 시간 동안 최대한 점수를 많이 받을 수 있도록 전략적으로 풀려고 합니다.

예를 들어 3점짜리 2문제, 2점짜리 1문제, 1점짜리 3문제로 총 6문제라고 해봅시다.
그리고 시험은 3초가 남아 많아야 3문제밖에 못 푸는 상황입니다.
이 경우엔 3점짜리 2문제, 2점짜리 1문제를 풀어 8점을 받는 것이 가장 이득입니다.

윤철이가 열심히 문제를 푸는 동안, 윤철이가 받을 수 있는 최고 점수를 구해주세요.

첫째 줄에 문제의 수 N(1 ≤ N ≤ 10⁹), 서로 다른 배점의 수 M(1 ≤ M ≤ 10⁵), 남은 시험 시간 K(0 ≤ K ≤ N)초가 차례로 주어집니다.

둘째 줄부터 M개의 줄에 걸쳐, 배점 S_i(1 ≤ S_i ≤ 10⁶)와 해당 배점을 가진 문제의 수 P_i(1 ≤ P_i ≤ 10⁹)가 주어집니다.

또 주어진 값들은 다음과 같은 조건을 추가로 만족합니다.

• i ≠ j 이면, S_i ≠ S_j
• P₁ + P₂ + P₃ + ... + P_M = N

윤철이가 최선을 다해서 풀었을 때, 받을 수 있는 최고 점수를 출력합니다.

5점짜리 문제 3개, 2점짜리 문제 5개, 7점짜리 문제 2개로 총 10문제가 있습니다.
시간이 7초밖에 없으므로 5점 3개, 2점 2개, 7점 2개를 풀면 5*3 + 2*2 + 7*2 = 33점을 받을 수 있고, 이 점수보다 높은 점수를 받을 수는 없습니다.