34235번 - 극한의 효율 빌런

문제

숭고한 대학의 프로그래밍 과목에서는 특이한 과제가 출제되었다. 학생들에게는 $N$개의 아이템이 주어지며, 각 아이템은 특정한 가치($v_i$)와 비용($c_i$)을 가지고 있다. 학생들은 이 중 일부 아이템을 골라 그 가치의 합이 최소 $K$ 이상이 되도록 선택하면 과제 만점을 받을 수 있다.

하지만, 이 과제를 단순히 만점으로 끝내고 싶지 않은 학생이 있었다. 그는 바로 숭고한 대학의 유명한 "극한의 효율 빌런"이다. 이 학생은 단순히 가치 합이 $K$ 이상인 조합을 넘어서, 선택된 아이템들의 비용 평균이 가능한 작도록 만들고자 한다.

빌런 덕분에 더 어려워진 과제를 해야 하는 숭고한 학생을 위해 가치의 합이 $K$ 이상이 되도록 아이템을 선택했을 때, 선택된 아이템들의 비용 평균의 최솟값을 구해주자. (단, 비용의 평균이 정수가 아닌 경우 소숫점 아래는 버림한다.)

입력

첫째 줄에 두 정수 $N$과 $K$가 주어진다. $(1 \le N \le 1,000,円\ 1 \le K \le 5,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 각 아이템의 정보가 주어진다.

각 줄에는 두 정수 $v_i$와 $c_i$가 공백으로 구분되어 주어지며, 각각 아이템의 가치와 비용을 의미한다. $(1 \le v_i \le 5,000,円\ 1 \le c_i \le 10^9)$

또한, $K \le \displaystyle\sum_{i=1}^{N} v_i \le 5,000円$ 를 만족한다.

출력

첫째 줄에 가치의 합이 $K$ 이상이 되도록 아이템을 선택했을 때, 선택된 아이템들의 비용 평균의 최솟값을 출력한다. (단, 비용의 평균이 정수가 아닌 경우 소숫점 아래는 버림한다.)

제한

힌트