問題文

コンピューターゲーム Toaru Fantasy では $N$ bit の符号付き整数 (2の補数) を用いて様々な数値を管理しています。

Toaru Fantasy には最近オーバーフローバグが見つかり、これを利用した攻略法が研究されています。
通常、敵を攻撃し、 敵の体力を 0 以下にするとその敵を撃破できます。
一方オーバーフローバグ攻略法では、 敵の体力をわざと回復し、 オーバーフローで体力が 0 以下になったときにも撃破判定されることを利用して敵を撃破します。

敵の初期体力を $X$ 、 1回の攻撃で減少させられる敵の体力を $A$ 、 1回の回復で増加させられる敵の体力を $B$ とします。
攻撃・回復ともに1回当たり1単位時間かかるとき、敵を撃破するのに必要な最短時間を求めてください。
敵が自らの体力を増減させることはありません。

2の補数知らない方向け情報

ある整数 $x (-2^{N-1} \leq x < 2^{N-1})$ は $N$ bit 符号付き整数で
$$ x = - 2^{n-1} * a_{n-1} + \sum_{k=0}^{k < n-1} 2^k * a_k $$
となるようなビット列 $a_{n-1}, a_{n-2}, \dots, a_{3}, a_{2}, a_{1}$ ($a_i$ = 0 または 1) を用いて表すことが出来ます (参考 : 二進法)

すなわち、各ビットが表す数は下の表のようになります。

 bit  |   N-1  |  N-2  | ... | 3 | 2 | 1 | 0 
------|--------|-------|-----|---|---|---|---
value |-2^(N-1)|2^(N-2)| ... | 8 | 4 | 2 | 1 

また、 二つの整数 $x,y (-2^{N-1} \leq x,y < 2^{N-1})$ の加算処理は通常の整数型と同様です。 最上位ビットより左に飛び出た分(carry flag)は無視されます。
https://en.wikipedia.org/wiki/Two%27s_complement#Addition

疑似コードで書くとこのような感じです。

// Bit Array A + B => C
carry = 0
for i in [0, N) :
    C[i] = (A[i] + B[i] + carry) % 2
    carry = floor( (A[i] + B[i] + carry) / 2 )

return C

入力

$N$
$X$
$A$
$B$

1行目にゲームで使われる整数型のビット長 $N$ が与えられます。
2行目に敵の最初の体力 $X$ が与えられます。
3行目に1回の攻撃で減少させられる敵の体力 $A$ が与えられます。
4行目に1回の回復で増加させられる敵の体力 $B$ が与えられます。

入力は全て整数で与えられます
$2\leq N \leq 32$
$1\leq X,A,B < 2^{N-1}$

出力

敵を撃破するのに必要な最短時間を出力してください。

サンプル

4
4
3
1

2

  0100 ( 敵の体力 4 )
+)1101 ( -A(=-3) を 2 の補数で表現 )
------
  0001 ( 残り体力 1 )

  0001 ( 敵の体力 1 )
+)1101 ( -A(=-3) を 2 の補数で表現 )
------
  1110 ( 残り体力 -2 )

4
6
2
1

2

  0110 ( 敵の体力 6 )
+)0001 ( B(=1) )
------
  0111 ( 残り体力 7 )

  0111 ( 敵の体力 7 )
+)0001 ( B(=1) )
------
  1000 ( 残り体力 -8 )

26
16777221
20
20

838861