AT_awtf2024_c Fuel

[problemUrl]: https://atcoder.jp/contests/awtf2024-open/tasks/awtf2024_c 以下の問題を $ T $ 個のテストケースについて解いてください． 今あなたは数直線上の座標 $ 0 $ の位置におり，これから座標 $ L $ まで移動したいです． 移動には車を使用します． この車はタイプ $ 1 $ とタイプ $ 2 $ の $ 2 $ 種類の燃料で動きます． 各タイプについて，そのタイプの燃料タンクの容量は $ C $ リットルです． 現在，両タイプの燃料タンクは満タンです． 車は，いずれかのタイプの燃料を $ x $ リットル ($ x $ は燃料の残量を超えない任意の正整数) 消費することで，数直線上を好きな方向に距離 $ x $ だけ移動できます． どちらのタイプの燃料を使用するかは，移動の度にあなたが選ぶことができます． 数直線上には $ N $ 個の燃料ステーションがあります． $ i $ 番目の燃料ステーションは座標 $ X_i $ にあります． 車がちょうど座標 $ X_i $ に存在するとき，タイプ $ K_i $ の燃料を $ 1 $ リットルあたりコスト $ 1 $ で買えます． もちろん，タンクの容量を超えて燃料を買うことはできません． 座標 $ L $ に到達することが可能かどうか判定し，可能ならば燃料の購入にかかるコストの総和の最小値を求めてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ L $ $ C $ $ X_1 $ $ X_2 $ $ \cdots $ $ X_N $ $ K_1 $ $ K_2 $ $ \cdots $ $ K_N $

$ T $ 行出力せよ． $ i $ 行目には，$ i $ 番目のテストケースについて，座標 $ L $ へ到達することが不可能なら $ -1 $ を出力し，可能ならコストの総和の最小値を出力せよ．

### 制約 - $ 1\ \leq\ T\ \leq\ 250000 $ - $ 1\ \leq\ N\ \leq\ 5000 $ - $ 1\ \leq\ L\ \leq\ 10^9 $ - $ 1\ \leq\ C\ \leq\ 10^9 $ - $ 0\