$Description$

从前有一个迷宫，迷宫的外形就像一棵带根树，每个结点（除了叶子结点外）恰好有 KK 个儿子。

一开始你在根结点，根结点的 KK 个儿子分别标记为‘A’, ‘B’, ‘C’….,而结点‘A’的 KK 个儿子结点分别标记为‘AA’,‘AB’,‘AC’……，依此类推。这棵树一共有 LL 层。

现在你事先知道 MM 个结点中有金子，并且你可以派出 NN 个机器人去收集金子。首先你可以分别指定每一个机器人的目标结点，于是这些机器人就会收集从根结点到其目标结点这条路径上（包括目标结点）所有的金子，但是每个位置的金子只能被收集一次。

现在你需要制定一个目标的分配方案，使得收集到的金子最多。

$Input$

输入的第一行有 4 个整数：M,K,L,N。对应题目描述中的参数。

接下来 M 行，每行是一个字符串，表示所对应的结点上有金子。

$Output$

输出利用 N 个机器人所能捡到时最多几个结点上的金子。

$Sample$ $Input$#1

5 3 3 1
ACC
ACB
AB
AC
A

$Sample$ $Input$#2

5 3 3 1
ACC
ACB
AB
AC
A

$Sample$ $Output$#1

3

$Sample$ $Output$#2

4

$Hint$

对于 $20\%$ 的数据，有 $1\le M\le 20$。
对于 $40\%$ 的数据，有 $1\le M\le 2000$。
对于 100%100% 的数据，有 $1\le M\le 50000,1\le K\le 26,1\le L\le 50,1\le N\le 10$。

$Train$ $of$ $Thought$

先将含有金子的点建一棵树
就是按原先的父子或爷爷和子孙的关系建树
没有金子的点可以不用加进树里面
然后用一个树形DP
设$f[i][j]$为前$i$个点派出$j$个机器人能捡多少金子

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;int h[50005], F[50005][15], T[50005];
int sum, n, m, l, r, t;
string A[50005];
string s;struct wh_
{int w, h;
}wh[50005];void hw(int x, int y)
{wh[++t] = (wh_){y, h[x]}, h[x] = t;}int Find(string k)//二分找父辈
{l = 1, r = n;while(l < r){int mid = (l + r) / 2;if(A[mid] < k)l = mid + 1;else r = mid;}return (A[r] == k) ? r : 0;//判断是否有这一个父辈
}void DP(int k)
{for(int l = h[k]; l; l = wh[l].h){DP(wh[l].w);for(int i = m; i >= 1; --i)for(int j = 1; j <= i; ++j)F[k][i] = max(F[k][i], F[wh[l].w][j] + F[k][i - j]);}for(int i = 1; i <= m; ++i)F[k][i] += T[k];
}int main()
{scanf("%d%d%d%d", &n, &l, &r, &m);for(int i = 1; i <= n; ++i)cin>>A[i], A[i] = ' ' + A[i];n++;A[n] = " ";sort(A + 1, A + n + 1);//排个序for(int i = 2; i <= n; ++i){int j = 0; s = A[i];while(j == 0)//找父辈{s.erase(s.length() - 1, 1);j = Find(s);}hw(j, i);//建树T[i] = 1;//这个点有一个金子}DP(1);printf("%d", F[1][m]);return 0;
}