뷔페에서 접시 채우기

정해진 코스 대신 원하는 만큼 먹을 수 있는 뷔페식 점심과 저녁을 파는 식당이 있다. 배고픈 학생에게는 대개 이쪽이 이득이다. 앨리스는 뷔페를 좋아하지만 접시를 어떻게 채워야 가장 좋은지 늘 고민한다. 앨리스는 메뉴에 오른 $n$가지 음식마다 가치를 다르게 매긴다. 접시 넓이가 한정되어 있고 음식마다 준비된 양도 한정되어 있는데, 이 제약 아래에서 접시에 담은 가치의 합을 최대로 만들려고 한다. 다행히 메뉴의 음식은 모두 나누기 쉬워서 앨리스는 각 음식을 원하는 만큼만 덜어 갈 수 있다. 앨리스가 접시를 채우도록 도와주자.

입력은 $n + 2$개의 줄로 이루어진다.

• 첫째 줄에 메뉴에 오른 음식의 가짓수 $n$이 주어진다.
• 둘째 줄에 앨리스의 접시 넓이 $a$가 주어진다. 단위는 mm$^2$이고 정수이다.
• 이어지는 $n$개의 줄에는 음식 하나의 정보가 공백으로 구분된 두 정수로 주어진다. 첫 번째 정수는 앨리스가 매긴 음식 $i$의 mm$^2$당 가치 $v_i$이다. 두 번째 정수는 음식 $i$를 남김없이 접시로 옮겼을 때 차지하는 넓이 $a_i$이고, 단위는 mm$^2$이다.

제한

• $1 \le n \le 1000$
• $0 \le a \le 100000$
• $0 \le i \le n - 1$인 모든 $i$에 대해
  • $0 \le v_i \le 100$
  • $0 \le a_i \le 100000000$

앨리스가 접시에 담을 수 있는 가치의 최댓값을 정수 하나로 한 줄에 출력한다. 넓이와 단위 가치가 모두 정수이므로 이 최댓값은 항상 정수이다.