Potyczki Algorytmiczne 已經開始了！遺憾的是，Bajtazar 不能荒廢他的工作，而他的職責也不會因為比賽週而神奇地消失。我們可以將 Bajtazar 的一天視為 $n$ 個時段，每個時段持續一「位元組小時」（bajtogodzina）。每個時段的職責屬於以下三類之一：

1. 辦公室會議，
2. 遠端會議，
3. 無職責。

在一天之中，Bajtazar 可能待在家裡、辦公室，或是在兩地之間的路上。Bajtazar 的一天始於家中，也終於家中。他最多可以前往辦公室一次，前提是他必須在第 $n$ 個時段結束前回到家。從家到辦公室以及從辦公室回家的路程各需耗時 $t$ 個位元組小時。根據他所在的位置，Bajtazar 可以採取不同的行動：

• 在家：Bajtazar 當然無法參加辦公室會議，他可以（但不一定要）參加遠端會議，或者可以解決 Potyczki Algorytmiczne 的遠端比賽題目（但他不能在參加會議的同時解決題目）。
• 在路上：Bajtazar 無法參加任何會議，也無法解決題目——他必須專心開車（他請不起司機）。
• 在辦公室：Bajtazar 可以參加任何類型的會議，而在會議之外的時間他必須工作——此時他不能解決題目。

你的任務是規劃 Bajtazar 的一天，以最大化他解決題目的總位元組小時數。然而，如果 Bajtazar 錯過超過 $k$ 場會議，他可能會被解僱。那樣的話，他參加明年比賽的機會，就像許多其他人生大事一樣，將會變得懸而未決——我們不希望這種情況發生。

Bajtazar 非常有條理，因此在每個時段他都專注於做一件確定的事情，特別是往返於家與辦公室的行程，每次都會佔用他連續 $t$ 個完整的時段。

輸入格式

第一行包含三個整數 $n$、$k$ 以及 $t$ ($3 \le n \le 8000, 0 \le k \le n, 1 \le t < \frac{n}{2}$)，分別代表時段總數、Bajtazar 可以錯過的會議數量，以及往返家與辦公室單程所需的交通時間（以位元組小時為單位）。

第二行包含一個長度為 $n$ 的字串，由字元 1、2 或 3 組成，代表 Bajtazar 在一天中各個時段的職責類型。這些數字對應於前述的類別編號。

輸出格式

輸出一個整數，代表 Bajtazar 在不錯過超過 $k$ 場會議的前提下，能夠用來解決題目的總位元組小時數。如果無法在錯過不超過 $k$ 場會議的情況下完成行程，請輸出 $-1$。

範例

範例 1

輸入

10 1 2
3233313132

輸出

3

範例 2

輸入

7 0 2
3313233

輸出

0

範例 3

輸入

6 5 1
231323

輸出

6

範例 4

輸入

4 1 1
1331

輸出

-1

說明

範例說明：在第一個範例中，其中一個最佳解法是 Bajtazar 的行程安排如下：

1. 解決題目
2. 在家參加遠端會議
3. 解決題目
4. 前往辦公室
5. 前往辦公室
6. 辦公室會議
7. 回家
8. 回家（錯過一場會議）
9. 解決題目
10. 在家參加遠端會議

在這個計畫中，Bajtazar 錯過了一場會議，並解決了 3 個位元組小時的題目。

在第二個範例中，Bajtazar 不會被解僱的唯一計畫如下：

1. 前往辦公室
2. 前往辦公室
3. 辦公室會議
4. 辦公室工作
5. 在辦公室參加遠端會議
6. 回家
7. 回家

在第三個範例中，Bajtazar 可以整天待在家裡，解決題目並跳過所有遠端會議。

在第四個範例中，Bajtazar 無法參加辦公室會議，因為他無法及時趕到辦公室或無法及時趕回家。