英雄であるあなたは、世界の最終ボス Irisu と戦おうとしています。英雄として、あなたには身体 $B$、精神 $M$、知性 $I$ という $3$ つのキャラクター「能力」があり、総合的な強さ $S$ はこれらの能力の幾何平均で計算されます。つまり、$S=\sqrt[3]{BMI}$ です。残念なことに、前回のボスとの戦いに負けたため、現在すべての能力がゼロになっています。

Irisu を倒すには、総合的な強さが神秘的な不等式 $(S+5)(S+1)(S+4)\ge X$ を満たす必要があります。この不等式は、前回の戦いの後に巨大なトマトの中で見つけた古代の巻物に書かれています。能力を上げる唯一の方法は、闇の錬金術師 Skyly から能力ポーションを買うことです。Skyly は $N_B+N_M+N_I$ 個のポーションを販売しています。最初の $N_B$ 個は身体ポーション、続く $N_M$ 個は精神ポーション、最後の $N_I$ 個は知性ポーションです。$i$ 番目のポーションは $P_i$ ドルで、対応する能力を $E_i$ ポイント増加させます。

世界と財布の両方を救うために、最終ボスを倒す能力ポーションの購入に必要な合計金額の最小値を求めたいと考えています。

入力

最初の行には $4$ つの整数 $X,N_B,N_M,N_I$ が含まれます。続く $N_B+N_M+N_I$ 行のうち $i$ 番目の行には $2$ つの整数 $P_i,E_i$ が含まれます。

• $0\le X\le10^9$
• $0\le N_B,N_M,N_I\le30$
• $0\le P_i,E_i\le10^9$ すべての $1\le i\le N_B+N_M+N_I$ に対して。

出力

最終ボスを倒す能力ポーションの購入に必要な合計金額の最小値を出力してください。Skyly からすべてのポーションを買っても十分な強さにならない場合は、DEAREST DROP を出力してください。

入出力例

入力 1

31 4 1 5
9 2
6 5
3 5
8 9
7 9
3 2
3 8
4 6
2 6
4 3

出力 1

12

入力 2

5566 2 1 0
0 999999999
999999999 0
0 0

出力 2

DEAREST DROP

入力 3

50216 2 2 2
1 20
1 30
10 42
20 43
15 18
17 19

出力 3

29