15407번 - How to Eat at a Buffet 다국어

문제

Instead of a seated meal, some restaurants offer all-you-can-eat buffet lunches and dinners. This is usually a bargain for famished students. Alice likes such buffet meals, but is always worried about how best to fill her plate with food. She values the n different items on the menu differently, and her goal is to have as much value as she can on her plate, constrained by the limited area of the plate and the limited availability of some menu items. Luckily, items on the menu are easily dividable and Alice can take an arbitrary fraction of each dish. Can you help her fill her plate?

입력

The input is formed of n + 2 lines:

• the first line consists of the number n of different items on the menu;
• the second line consists of the area a of Alice’s plate, an integer in mm²;
• each of the n remaining lines consists of information about a menu item, as two integers separated with a space; the first one is the value v_i of item i per mm², as perceived by Alice; the second one is the area a_i, in mm², that item i would occupy if Alice were to transfer it fully to her plate.

Limits

• 1 ≤ n ≤ 1 000
• 0 ≤ a ≤ 100 000
• For every 0 ≤ i ≤ n − 1:
  • 0 ≤ v_i ≤ 100;
  • 0 ≤ a_i ≤ 100 000 000.

출력

A single line consisting of an integer: the maximal value that Alice can fit on her plate.

제한

힌트