AT_bogosortcontest_div2_g Fair Problem Set

soryuusi 君、jastaway 君、tatesoto 君の $ 3 $ 人は、競技プログラミングのコンテストを開催することにしました。 $ 3 $ 人はそれぞれ $ X $ 問、 $ Y $ 問、 $ Z $ 問の問題を作りました。 合計 $ M = X + Y + Z $ 問の問題には $ 1 $ から $ M $ までの番号がついており、以下のようになっています。 - $ 1 \leq i \leq X $ のとき、作者は soryuusi 君です。 - $ X+1 \leq i \leq X+Y $ のとき、作者は jastaway 君です。 - $ X+Y+1 \leq i \leq M $ のとき、作者は tatesoto 君です。 各問題 $ i $ には難易度 $ D_i $ と、作者の好み度 $ F_i $ が設定されています。 この中から $ N $ 問を選んで、コンテストの問題セットを作ります。コンテストには $ N $ 個の問題枠があり、 $ j $ 番目 ( $ 1 \leq j \leq N $ ) の問題枠には「ターゲット難易度 $ T_j $ 」が設定されています。 コンテストの質を保ち、かつ $ 3 $ 人が平等に貢献するために、以下の条件をすべて満たすように問題を選ぶ必要があります。 - 各問題枠にはちょうど $ 1 $ つの問題を割り当てる。ある問題 $ i $ を $ j $ 番目の問題枠に割り当てるには、難易度の差が $ K $ 以下、すなわち $ |D_i - T_j| \leq K $ を満たす必要がある。 - soryuusi 君、jastaway 君、tatesoto 君の $ 3 $ 人は、それぞれ $ L $ 問以上 $ R $ 問以下の問題を問題セットに提供する必要がある。 - 同じ問題を複数の問題枠に割り当てることはできない。 条件を満たす問題の選び方が存在するか判定し、存在する場合は、選ばれた $ N $ 問の好み度の合計の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ L $ $ R $ $ T_1 $ $ T_2 $ $ \ldots $ $ T_N $ $ X $ $ Y $ $ Z $ $ D_1 $ $ F_1 $ $ D_2 $ $ F_2 $ $ \vdots $ $ D_{X+Y+Z} $ $ F_{X+Y+Z} $

条件を満たす問題の選び方が存在するとき、好み度の合計の最大値を出力せよ。 条件を満たす問題の選び方が存在しないとき、`-1` と出力せよ。

### Sample Explanation 1 以下のように問題を割り当てることで、好み度の合計 $ 2 + 5 + 7 + 5 = 19 $ を達成できます。 - ターゲット難易度 $ 400 $ の問題枠 $ 1 $ に、問題 $ 2 $ （作者 soryuusi 君、難易度 $ 100 $ 、好み度 $ 2 $ ）を割り当てる。 - ターゲット難易度 $ 700 $ の問題枠 $ 2 $ に、問題 $ 5 $ （作者 tatesoto 君、難易度 $ 800 $ 、好み度 $ 5 $ ）を割り当てる。 - ターゲット難易度 $ 1200 $ の問題枠 $ 3 $ に、問題 $ 4 $ （作者 tatesoto 君、難易度 $ 1600 $ 、好み度 $ 7 $ ）を割り当てる。 - ターゲット難易度 $ 2000 $ の問題枠 $ 4 $ に、問題 $ 3 $ （作者 jastaway 君、難易度 $ 1900 $ 、好み度 $ 5 $ ）を割り当てる。 どの問題枠も、ターゲット難易度と実際の難易度の差は $ 400 $ 以下になっています。 また、soryuusi 君、jastaway 君、tatesoto 君が提供した問題数はそれぞれ、 $ 1 $ 問、 $ 1 $ 問、 $ 2 $ 問となり、「 $ 1 $ 問以上 $ 2 $ 問以下」という制約を満たします。 よって、この割り当て方は条件を満たします。 好み度の合計が $ 19 $ を超えるような条件を満たす割り当て方は存在しないことが証明できるので、 $ 19 $ を出力します。 ### Sample Explanation 2 問題枠に対して問題数が足りないため、条件を満たす割り当て方は存在しません。 ### Sample Explanation 3 例えば、問題枠 $ 1 $ に問題 $ 4 $ 、問題枠 $ 2 $ に問題 $ 5 $ 、問題枠 $ 3 $ に問題 $ 9 $ を割り当てることで、好み度の合計 $ 97 + 96 + 92 = 285 $ を達成できます。 ### Constraints - $ 1 \leq N \leq 150 $ - $ 0 \leq K \leq 1000 $ - $ 1 \leq X, Y, Z \leq 100 $ - $ 0 \leq L \leq R \leq 100 $ - $ 1 \leq T_j \leq 3000 $ ( $ 1 \leq j \leq N $ ) - $ 1 \leq D_i \leq 3000 $ ( $ 1 \leq i \leq X+Y+Z $ ) - $ 1 \leq F_i \leq 10^9 $ ( $ 1 \leq i \leq X+Y+Z $ ) - 入力される数値はすべて整数