部分点解法です。

（当初は \(k\) が \(1\) 種類の問題をそのまま出題する予定でしたが、Testerによりこちらの解法が提案されたため、部分点として設定されました）。

赤い勲章のことだけを考え、最後に答えを \(2\) 倍します。\(k_1 = k_2 = k\) と表記します。

攻撃 \(2\) は、勲章を貰えない場合に行ったとしても、得をしません。また、余分なダメージ（ \(k\) よりも大きなダメージ）を与えても、得をしません。

以上のことから、最適な戦略であって、「攻撃 \(1\) を複数回」→「攻撃 \(2\) を複数回」→「攻撃 \(1\) を複数回」という形になっているものが存在します。

ここで、攻撃 \(2\) を行う回数を固定します。（ \(m\) とします。）すると、結局必要なのは、「\(\{h_i\}\) の配列を前半と後半に分けて、【前半部分で \(h_i \geq k\) を満たす \(i\) の数】＋【後半部分で \(h_i \geq k + m\) を満たす \(i\) の数】の最大化、ただし後半部分で \(h_i \geq m\) を満たす \(i\) の数が \(k\) 」となります。

これは、\(m\) をインクリメントしながら、後半部分を左方向に伸ばし続けていくことで、全ての \(m\) に対して最大値を求めることができ、それらにより答えを更新していけば良いです。