당신이 응원하는 축구 팀이 장애 아동을 돕기 위한 전 세계 모금 활동의 일환으로 열리는 자선 토너먼트에 참가하고 있습니다. 이 토너먼트는 일반적인 축구 대회와 동일하게 진행되며, 한 경기에서 승리한 팀은 3점, 패배한 팀은 0점을 얻습니다. 경기가 무승부일 경우 양 팀 모두 1점씩 얻습니다.
당신의 팀은 토너먼트 1단계에서 총 $N$경기를 치렀고, 이 단계는 이제 막 끝났습니다. 이 중에서 더 많은 승점을 얻은 일부 팀들만이 2단계로 진출하게 됩니다.
하지만 이 토너먼트의 주요 목적은 기금 모금이기 때문에, 2단계 진출 팀이 결정되기 전에 각 팀은 추가 골을 구매할 수 있는 기회가 주어집니다. 이 추가 골들은 실제 경기에서 넣은 골처럼 인정되며, 이미 치른 경기 결과를 바꾸는 데 사용할 수 있습니다.
당신의 팀은 최대 $G$개의 골을 구매할 수 있는 예산을 가지고 있습니다. 다른 팀들은 골을 구매하지 않는다고 가정할 때, 당신의 팀이 얻을 수 있는 최대 승점을 구하세요.
입력
첫 번째 줄에 두 정수 $N (1 \leq N \leq 100,000), G (0 \leq G \leq 1,000,000)$ 가 주어집니다.
$N$: 경기 수
$G$: 구매 가능한 골 수
다음 N개의 줄에는 각 경기 결과가 주어집니다. 각 줄에는 두 정수 $S, R (0 \leq S, R \leq 100)$이 주어지며,
jtw7913 7달 전 1
문제
당신이 응원하는 축구 팀이 장애 아동을 돕기 위한 전 세계 모금 활동의 일환으로 열리는 자선 토너먼트에 참가하고 있습니다. 이 토너먼트는 일반적인 축구 대회와 동일하게 진행되며, 한 경기에서 승리한 팀은 3점, 패배한 팀은 0점을 얻습니다. 경기가 무승부일 경우 양 팀 모두 1점씩 얻습니다.
당신의 팀은 토너먼트 1단계에서 총 $N$경기를 치렀고, 이 단계는 이제 막 끝났습니다. 이 중에서 더 많은 승점을 얻은 일부 팀들만이 2단계로 진출하게 됩니다.
하지만 이 토너먼트의 주요 목적은 기금 모금이기 때문에, 2단계 진출 팀이 결정되기 전에 각 팀은 추가 골을 구매할 수 있는 기회가 주어집니다. 이 추가 골들은 실제 경기에서 넣은 골처럼 인정되며, 이미 치른 경기 결과를 바꾸는 데 사용할 수 있습니다.
당신의 팀은 최대 $G$개의 골을 구매할 수 있는 예산을 가지고 있습니다. 다른 팀들은 골을 구매하지 않는다고 가정할 때, 당신의 팀이 얻을 수 있는 최대 승점을 구하세요.
입력
각 줄에는 두 정수 $S, R (0 \leq S, R \leq 100)$이 주어지며,
를 의미합니다 (추가 골 구매 전 기준).
출력
추가 골을 적절히 사용했을 때, 당신의 팀이 얻을 수 있는 최대 총 승점을 출력하세요.