第 14 回 日本情報オリンピック　模擬予選 ３

2014年12月13日
kagamiz

問題

ミズゴロウのゴロウくんは, 大好きなキャシーに好かれているかどうかを花占いで確かめることにした.

ゴロウくんは, 花占いを行うにあたって, 庭に生えている N 個の花を使うことにした. i (1 ≦ i ≦ N) 番目の花には花びらが Ai 枚あり, 美しさが Bi である. ゴロウくんはこの中から 花を 0 個以上選び, 選んだ花の全ての花びらを抜く. 抜いた花びらの枚数が奇数であると, ゴロウくんは (選んだ花の個数) × C だけ幸せ度が得られる. 抜いた花びらの枚数が偶数であると, ゴロウくんは (選んだ花の個数) × D だけ幸せ度が得られる. ただし, どちらの場合にも選んだ花の美しさの和だけ, 幸せ度が下がる.

ゴロウくんは, 花占いによって得られる幸せ度を最大化したい. ただし, 花占いをする前のゴロウくんの幸せ度は 0 である. また, ゴロウくんはこの花占いを 1 度しか行わない.

入力として N, C, D 及び N 個の花の情報が与えられるとき, ゴロウくんが適切に花を選んだときの幸せ度を最大化せよ.

入力

入力は N + 1 行からなる.
1 行目には, 整数 N, C, D ( 1 ≦ N ≦ 100, -1000 ≦ C, D ≦ 1000 ) が書かれている.
1 + i ( 1 ≦ i ≦ N ) 行目には, 整数 Ai, Bi ( 1 ≦ Ai ≦ 10000, -1000 ≦ Bi ≦ 1000 ) が書かれている.

出力

ゴロウくんが適切に花を選んだときの幸せ度の最大値を出力せよ.

入出力例

3 1 4
1 1
9 4
7 2

  

4 -10 -2
1 1
1 -1
1 1
1 1
  

3 -9 10
1 -5
2 5
2 5

  

5
   

0
   

10
   

入出力例 1 では, 1 番目の花と 3 番目の花を使って花占いをすると, 幸せ度 8 が得られる. ここから 1 番目の花と 3 番目の花の美しさの和を引くと, 幸せ度は 5 になる.

入出力例 2 のように, 選んだ花の個数にかけられる整数 C, D が負になることや, 美しさが負になることがあるということに注意せよ.

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．

採点用データ