축구

당신이 응원하는 축구팀이 자선 대회에 나섰다. 이 대회는 장애 아동을 돕는 국제 모금 활동의 하나로 열린다. 보통의 대회와 마찬가지로 경기를 이긴 팀은 3점을 얻고, 진 팀은 점수를 얻지 못한다. 무승부면 두 팀이 각각 1점을 얻는다.

당신의 팀은 방금 끝난 1차전에서 $N$경기를 치렀다. 2차전에는 누적 점수가 높은 일부 팀만 올라간다. 그런데 이 대회의 가장 큰 목적은 모금이므로, 2차전에 올라갈 팀을 정하기 전에 각 팀은 골을 추가로 살 수 있다. 사들인 골은 경기장에서 직접 넣은 골과 똑같이 취급되고, 그 팀이 치른 어느 경기의 결과를 바꾸는 데든 쓸 수 있다.

당신의 팀은 예산으로 골을 최대 $G$개까지 산다. 산 골은 원하는 경기에 마음대로 나눠 넣을 수 있고, 한 경기에 여러 개를 넣어도 된다. 다른 팀은 골을 사지 않는다고 할 때, 골을 사고 난 뒤 당신의 팀이 얻을 수 있는 최대 총점을 구하라.

첫째 줄에 정수 $N$과 $G$가 주어진다 ($1 \le N \le 10^5$, $0 \le G \le 10^6$). $N$은 당신의 팀이 치른 경기 수, $G$는 살 수 있는 골의 최대 개수다.

다음 $N$개 줄에는 경기 결과가 한 줄에 하나씩 정수 $S$와 $R$로 주어진다 ($0 \le S, R \le 100$). $S$는 골을 사기 전 그 경기에서 당신의 팀이 넣은 골 수, $R$은 상대에게 허용한 골 수다.

골을 사고 난 뒤 당신의 팀이 얻을 수 있는 최대 총점을 한 줄에 출력한다.