BoB005-G: Butter Thief

2 secs 1024 MB
kyaneko999

問題


Sakky さんは から までの番号がついたバターを 個ずつ持っています. 番目のバターの美味しさは です.
ただし, はフィボナッチ数列の第 項であり,以下のように定義されます.

  • に対して

Sakky さんはバター泥棒に襲われやすい体質です.
バター泥棒にはそれぞれレベルが定められており,レベル のバター泥棒は美味しさが 以下のバターしか盗むことができません.
バター泥棒が Sakky さんを襲うときには,Sakky さんが持っているバターの中でなるべく美味しさが大きいものを 個盗みます.
レベル のバター泥棒が 人ずつ現れ Sakky さんを襲うとき,盗まれるバターの番号の総和を求めてください.

制約


  • 入力はすべて整数

入力


入力は以下の形式で標準入力から与えられる.

出力


答えを整数で出力しなさい.

入出力例


入力例1
2 5
出力例1
12

Sakky さんが持っているバターの美味しさは番号順に です.
レベル のバター泥棒は美味しさが 以下のバターを盗むことができます.よって,Sakky さんを襲うと 番目のバターを盗んでいきます.
レベル のバター泥棒は美味しさが 以下のバターを盗むことができます.よって,Sakky さんを襲うと 番目のバターを盗んでいきます.
レベル のバター泥棒は美味しさが 以下のバターを盗むことができます.よって,Sakky さんを襲うと 番目のバターを盗んでいきます.
レベル のバター泥棒は美味しさが 以下のバターを盗むことができます.よって,Sakky さんを襲うと 番目のバターを盗んでいきます.
したがって,盗まれるバターの番号の総和は です.

入力例2
1 10000000000000000
出力例2
746583271651532394

Submit


Go (1.14)