#8 もういくつ寝ると和尚が2

難易度

## ストーリー $1$日目、この世界には和尚さんが$N$人いた… $1$日ごとに和尚さんは別の人を和尚さんに勧誘するので、人数が2倍になる しかし、政府の$M$回の粛清によって$D_i$日目には和尚さんが$L_i$人になるまで粛清されてしまう…! さて、この世界は和尚さんがちょうど$K$人になると平和になることが知られている。 この世界に平和が訪れることはあるのか…? 和尚さんがちょうど$K$人になるのが何日目か求めてください。もしくは、ならないことを判定してください。 ## 入力 $N$ $M$ $K$ $D_1$ $L_1$ $D_2$ $L_2$ $\vdots$ $D_M$ $L_M$ ## 出力 答えを1行で出力すること。 $K$人ちょうどになることがない場合は代わりに`-1`を出力すること。 ## 制約 $1 \le N \le 10^{18}$ $0 \le M \le 10^{6}$ $1 \le K \le 10^{18}$ $1 \le D_i \le 10^{18} (1 \le i \le M)$ $1 \le L_i \le 10^{18} (1 \le i \le M)$ $D_i \ne D_j (i \ne j)$ ## 入出力例 ### 例1 #### 入力 ``` 1 1 4096 10 1 ``` #### 出力 ``` 22 ``` 和尚さんの人数は次のように遷移します: $1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1024,2048,4096$