時間制限:1000ミリ秒
メモリ制限:65536KB
問題
牛はリンゴが好きであるというのは、少し知られている。農民ジョンは、彼の土地に、2本のリンゴの木(1,2番号付けられる)を持っている。リンゴが木の上にあるとき、ベッシーはリンゴを取れないので、リンゴが落ちるのを待たなければならない。しかし、リンゴが地面に着くとリンゴは傷つくので、ベッシーはリンゴを空中で捕らえなければならない。ベッシーはリンゴを空中で捕らえると、2、3秒で食べることができる。毎分、2本のリンゴの木のうち1本はリンゴを落とす。ベッシーが、その時リンゴが落ちる木の下にいたならば、ベッシーはリンゴを捕らえることができる。ベッシーは2本の木の間を速く(1分未満で)移動することができ、常に、1本の木の下のみに立っていることができる。しかし、ベッシーが2本の木の間を移動する気のある回数は限られている。リンゴはT分間(1 <= T <= 1000)落ち、ベッシーはW回(1 <= W <= 30)、2本の木の間を移動することができる。毎分、どの木が落ちるかが与えられたとき、ベッシーが捕らえることのできるリンゴの最大数を求めよ。ベッシーは、最初は木1にいる。
入力
入力の1行目には、2つの整数T,Wが空白区切りで書かれている。2行目以降のT行には、各分、どの木のリンゴが落ちるかを表す整数(1または2)が書かれている。
出力
ベッシーがW回より多く2本の木の間を移動することなく、得ることのできるリンゴの最大数を表す1つの整数を出力せよ。
入力の例
7 2 2 1 1 2 2 1 1
出力の例
6
ヒント
入力の詳細：7個のリンゴが落ちる。リンゴは、木2、木1、木1、木2、木2、木1、木1の順番で落ちる。ベッシーは、2回木の間を移動する気がある。
出力の詳細：木1の下で2個のリンゴが落ちるまで、ベッシーが木1の下に留まり、2個リンゴを捕らえた後、木2に移動し、2個のリンゴを捕らえ、その後木1に移動して、2個リンゴを捕らえると、6個のリンゴを捕らえることができる。
出典
USACO 2004 November