Description　　

一個字符串的權值是這個串包含的不同字符個數。

　　給定一個長度為n的字符串，把它分為k個連續非空字段，每個字符必須在某一段中，最小化字符串的權值和。

　　Input

　　第一行兩個數n，k，含義如題所述。

　　接下來一行一個長度為n的字符串，保證僅包含小寫英文字母。

　　Output

　　輸出最小權值。

　　Sample Input

　　輸入1：

　　12 3

　　abaacdddfe

　　輸入2：

　　50 35

　　acbdcfabcaedscdbcsbacbdcbbacjacbkabcjadkcbsjkckkza

　　Sample Output

　　輸出1：

　　6

　　樣例解釋1：

　　一種最優方案是分為：”abaa”， “cddd”和”feff”。

　　輸出2：

　　39

　　Data Constraint

　　對于10%的數據，n《=10。

　　對于30%的數據，n《=200。

　　對于50%的數據，n《=1500。

　　對于另外20%的數據，僅包含a和b兩種字母。

　　對于100%的數據，1《=k《=n《=100，000。

　　Solution

　　一個很顯然的dp：f［i］［j］表示到位置i，分為了j段，需要的最小代價

　　這有50分

　　可以發現，答案最大為段數+25

　　那么代價不會很大，可以放到狀態中

　　狀態改成f［i］［j］表示分了i段，代價為i+j最右可以到哪里

　　預處理一個a［i］［j］表示從位置i出發，花代價為j，最右可以到哪里

　　然后隨意轉移一下

　　但是，這么做是有bug的（數據里沒有，所以這樣就可以A了）

　　如果到某一次，最后剩下的位數已經不夠分K段了，前面就不能延伸到最后，這個取個min就行了