N - Activities Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

N 種類の活動、活動 1, 2, \dots N があります。 あなたは、これらの活動の中から 1 つ以上を選び、好きな順序で行います。 ただし、同じ活動を複数回行うことはできません。

現在のあなたの体力は H です。 活動 i を行うと、あなたは a_i \times{}(体力) 点の得点を得て、その後、体力が b_i 減ります。 (活動後、体力が 0 未満になることも許されます。)
あなたの得ることができる合計得点の最大値を求めてください。

制約

  • 入力は全て整数
  • 1 ≤ N ≤ 100
  • 1 ≤ H ≤ 10^5
  • 1 ≤ a_i, b_i ≤ 10^5

入力

入力は以下の形式で標準入力から与えられる。

N H
a_1 b_1
a_2 b_2
\vdots
a_N b_N

出力

答えを出力せよ。

入力例 1

4 6
4 1
3 2
2 3
1 4

出力例 1

45

例えば、以下のようにすると合計得点が 45 点になります。

  • 初め、体力は 6 である。
  • 活動 1 を行う。4 \times 6 = 24 点を得て、体力が 6 - 1 = 5 になる。
  • 活動 2 を行う。3 \times 5 = 15 点を得て、体力が 5 - 2 = 3 になる。
  • 活動 3 を行う。2 \times 3 = 6 点を得て、体力が 3 - 3 = 0 になる。

入力例 2

4 6
1 1
2 2
3 3
4 4

出力例 2

30

入力例 3

16 100
18 17
5 18
7 2
5 8
6 2
16 16
2 18
13 17
18 10
11 10
17 8
1 2
20 7
4 11
7 15
2 1

出力例 3

9282

Score : 6 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N kinds of activities: Activity 1, 2, \dots N. You will choose one or more from these activities and do them in the order you like. The same activity cannot be done multiple times.

Your current stamina is H. Doing activity i gets you a_i \times{}(stamina) points and decreases your stamina by b_i. (It is allowed to do an activity that makes your stamina less than 0.) Find the maximum total number of points you can get.

Constraints

  • All values in input are integers.
  • 1 ≤ N ≤ 100
  • 1 ≤ H ≤ 10^5
  • 1 ≤ a_i, b_i ≤ 10^5

Input

Input is given from Standard Input in the following format:

N H
a_1 b_1
a_2 b_2
\vdots
a_N b_N

Output

Print the answer.

Sample Input 1

4 6
4 1
3 2
2 3
1 4

Sample Output 1

45

One way to get a total of 45 points is as follows:

  • Your initial stamina is 6.
  • Do Activity 1. You get 4 \times 6 = 24 points and your stamina becomes 6 - 1 = 5.
  • Do Activity 2. You get 3 \times 5 = 15 points and your stamina becomes 5 - 2 = 3.
  • Do Activity 3. You get 2 \times 3 = 6 points and your stamina becomes 3 - 3 = 0.

Sample Input 2

4 6
1 1
2 2
3 3
4 4

Sample Output 2

30

Sample Input 3

16 100
18 17
5 18
7 2
5 8
6 2
16 16
2 18
13 17
18 10
11 10
17 8
1 2
20 7
4 11
7 15
2 1

Sample Output 3

9282