Иннополис で開催される2224年の全ロシア情報オリンピックでは、自分のクローンを作れる新世代のロボットが配達を行っています。家から出ることなく、窓から直接配達物を受け取れます。
最初は配達ロボットが1台だけあります。いつでも、最上部のロボットは自分の真上に1台以上の新しいロボットを作ることができます。こうしてロボットの縦の列ができます。各ロボットの高さは建物の1階分の高さと同じです。
配達中、同じクローンロボットからなる列は、寮の建物に沿って左から右へ移動します。ロボットのデータベースには注文の一覧があり、各注文について配達先の窓が分かっています。ロボットの列がある注文の窓の前を通るとき、その窓と同じ高さにロボットがいれば配達できます。
移動中、ロボットの構造物は障害物にぶつかることがあります。障害物を越えた後も移動を続けるのは、障害物より上にいたロボットだけです。それらは障害物のすぐ先の地面に、引き続き縦の列をなした状態で着地し、移動、新たなクローンの作成、注文の配達を続けることができます。
障害物と窓の間の距離は十分大きいため、障害物を越えている間にロボットが窓の前を通ることはありません。
注文を1件配達するごとに、配達会社は $p$ 暗号ルーブルを受け取ります。新しいロボットを1台作る費用は $c$ 暗号ルーブルです。最終的な利益は、注文の配達による収入の合計から、すべてのロボットの作成費用の合計を引いたものです。会社は利益を最大化したいと考えています。すべての注文を配達する必要はなく、ロボットはいつでも停止して配達を終了できます。
会社が得られる利益の最大値を求めてください。
入力
最初の行には4つの整数 $n,m,c,p$ ($0\le n,m\le100000$、$1\le c,p\le10^6$) が与えられます。それぞれ障害物の数、データベースにある注文の数、ロボットのクローンを1台作る費用、注文1件の配達料金です。
続く $n+m$ 行には、障害物と配達先の窓の情報が、ロボットの列が寮に沿って左から右へ進むときに出会う順番で与えられます。各行には2つの整数 $t_i,h_i$ ($1\le t_i\le2$、$1\le h_i\le10^6$) が含まれます。$t_i$ は物体の種類（$1$ は障害物、$2$ は窓）で、$h_i$ は階数を単位とした障害物の高さ、または窓がある階です。
ちょうど $n$ 個の物体が種類 $1$ で、残る $m$ 個の物体が種類 $2$ であることが保証されます。
出力
得られる利益の最大値を1つの数として出力してください。
小課題
| 小課題 | 得点 | $n$ の制約 | $m$ の制約 | 追加の制約 | 必要な小課題 |
|---|---|---|---|---|---|
| $1$ | $24$ | $n\le100$ | $m\le100$ | $h_i\le100$ | |
| $2$ | $12$ | $n=0$ | |||
| $3$ | $14$ | $n=1$ | |||
| $4$ | $15$ | $m=1$ | |||
| $5$ | $17$ | $c=1$、$p=10^6$。すべての障害物の高さが $1$ | |||
| $6$ | $18$ | 入出力例、$1$–$5$ |
入出力例
入力 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
出力 1
4
入力 2
1 3 1 5 2 2 2 1 1 9 2 1
出力 2
9
注記
最初の入出力例の最適な配達戦略の1つを、下の9枚の図に示します。この戦略では、2件目の注文を配達しても利益は増えません。
2番目の入出力例では、最初の注文を配達するためにロボットのクローンを一度作れば十分です。得られたロボットの構造物で2件目の注文を配達できますが、3件目の注文を配達するために追加のクローンを作ることは採算が合いません。