Problem : 217 - B. 乳酸vs乳堅

Special Judge

Problem Statistics

Solved Member: 19　　Submission: 146　　User Tried: 21

Statement:

乳酸！by 楊英鵬

HH在看完照片二三事後，便決定要辦一場活動來看看你是乳酸還是乳堅，HH用N張英文字卡擺放成一個字串，每張字卡背後都有不同的價值(一樣的字可能價值不同喔！)，而一個字串的價值等同於結尾字卡的價值，你的任務是將原本的字串分割成1~K段，並使得價值總和最高。

有趣的是，HH要求每個字串必須是美觀的，美觀的條件是使得字串的長度介於[A,B](即A<=length<=B)，因為當字串是美觀時，字串的價值也產生了改變！經過不可思議的力量，第i段的字串價值將變身為i倍，若你可以將長度為N的字串分割K段，並使得價值總和最高，你將證明你不是乳酸，而是乳堅！

Input:Output:

一個測試檔有多筆測試資料，第一行有一正整數T表示測試資料數量。

對於每筆測試資料第一行有四個正整數N, K, A, B，每個正整數的意義如敘述。

第二行有一個長度為N的字串，此字串由大小寫英文字母所構成。

第三行有N個正整數Vi，依序表示每張字卡的價值。

對於第i筆測試資料，請以"Case #i:"做開頭，詳細請參考Sample Output。

若可以將英文字卡分成K段美觀的字串，輸出一個數字表示價值總和，接下來的K行依序輸出一組可行的分割方法。若無法，則表示你是乳酸，輸出"Sorry, you're milk cheese." (不包刮雙引號)。

Sample Input:Sample Output:

4
5 2 2 3
abAbC
1 2 2 1 2
5 2 1 2
abcde
1 2 2 1 2
5 2 1 5
aaaaa
1 1 1 1 1
7 3 1 3
hanhanw
1 2 3 1 2 3 1

Case #1:
6
ab
AbC
Case #2:
Sorry, you're milk cheese.
Case #3:
3
aaaa
a
Case #4:
12
han
han
w

HINT:

就是蛋疼的女生版，反義詞是乳堅。再多的話自行遐想。

對於50%的測試資料，1<=N<=500。
對於100%的測試資料，1<=N<=5000，1<=K<=500，1<=A<=B<=5000，1<=Vi<=1000。

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1500ms	65536kb	10
3	3000ms	65536kb	10
4	5000ms	65536kb	10
5	5000ms	65536kb	10
6	5000ms	65536kb	10
7	5000ms	65536kb	10
8	5000ms	65536kb	10
9	5000ms	65536kb	10
10	5000ms	65536kb	10