AI 민주주의

문제

AI가 급부상하면서 AI 민주주의라는 새로운 말이 등장했다. AI 민주주의란 인터넷 공간에 자신을 완전히 복제한 가상 시민이 현실의 자신을 대신해 의사 결정을 내리도록 하는 제도이다. 평행세계의 ninegle, closeAI, andropic 회사는 이를 실현해 국민들의 참정권 행사율을 $100\%$까지 끌어올렸다.

정부는 새로운 정책안을 추진하기 전에 AI 민주주의 서비스를 이용해 가상 시민들의 반응을 살핀다. 반응은 좋음과 나쁨 두 가지뿐이다. 전체 가상 시민 중 $70\%$ 이상이 좋음이라고 반응하면 정부는 해당 정책안을 추진하려고 한다. 즉, 좋음 반응을 보이는 시민이 적어도 $\left\lceil \frac{7N}{10} \right\rceil$명 필요하다.

각 가상 시민 $i$는 법안에 대한 수용 한계치 $V_i$와 반발 계수 $W_i$를 가진다. 법안의 강도가 $X$일 때, 가상 시민 $i$의 반응은 다음과 같이 결정된다.

• $X \times W_i \le V_i$인 경우, 시민은 정책을 긍정적으로 평가하며 비용 없이 즉시 좋음을 누른다.
• $X \times W_i > V_i$인 경우, 시민은 원래 나쁨을 누른다. 하지만 정부는 알고리즘 피드를 조정하는 정책 홍보 예산을 투입해 이 반응을 좋음으로 강제 변환할 수 있다. 이때 필요한 예산은 $X \times W_i - V_i$원이다.

정부가 정책 홍보에 사용할 수 있는 총예산은 $B$원이다. 예산 $B$원을 초과하지 않으면서 전체 가상 시민의 $70\%$ 이상에게 좋음 반응을 얻을 수 있는 법안 강도 $X$의 최댓값을 구하시오.

$X$는 $0$ 이상의 정수이다.

입력

첫째 줄에 가상 시민의 수 $N$과 정부의 예산 $B$가 공백으로 구분되어 주어진다. $(1 \le N \le 100,000; 0 \le B \le 10^{14})$

다음 $N$개의 줄 중 $i$번째 줄에는 $i$번째 가상 시민의 수용 한계치 $V_i$와 반발 계수 $W_i$가 공백으로 구분되어 주어진다. $(0 \le V_i \le 10^9; 1 \le W_i \le 10^9)$

출력

예산 $B$원 안에서 전체 시민의 $70\%$ 이상, 즉 적어도 $\left\lceil \frac{7N}{10} \right\rceil$명의 좋음 반응을 얻을 수 있는 법안 강도 $X$의 최댓값을 출력한다.

예제 입력 1

5 10
10 1
20 2
15 1
5 5
30 3

예제 출력 1

11