#P5034. 果冻

果冻

题目背景

赛时答疑

数据已经修复

【生存世界】Steve:你们哪位 dalao 可以收留我啊 qwq……

在 Minecraft 一个很友善、和谐的服务器里面,Steve 很喜欢在里面畅游,服务器采用小镇机制,于是有很多小镇。有一个镇叫果冻镇,镇长长得很像喜欢吃果冻,他很喜欢对着镜子吃着 bling bling 的果冻。突然,他收到“捷报”,镇上不久就要造反。他吓了一跳,赶紧从床上跳了起来(qwq),吃了一口果冻(误),着手处理这件事情。

题目描述

镇上有一个镇长以及 n1n-1 个镇员,所有的镇员都有着他的直属上司 fif_i。每个镇镇员与镇长都有一个距离 did_i(也就是他与镇长之间上司的人数加 11)。镇长想要所有镇员都是自己的直属下司,也就是与他的距离为 11

他每分钟可以让自己的一个镇员变为自己的直属下司,在第 t(t>0)t (t > 0) 分钟的时候,(也就是每一分钟的意思,而 tt 将从 11 开始),这个镇员变为自己的直属下司,镇长可以收获 (di+t)&k (d_i+t) \& k 的安全指数(其中,&\& 为按位与运算)。然后这个镇员的下司都会跟着这个镇员一起变动(也就是这个镇员的直属下司仍然是这个镇员的,除非镇长把这个下司变为自己的直属下司)。

当所有镇员都是自己的直属下司后,镇长就可以安心吃他的果冻了。他现在想问你,应该怎样变动,才能使安全指数最大。因为镇长很想快点吃到果冻,他就把这个任务交给你了。

输入格式

第一行是两个正整数 nnkk(具体意义请见题目描述)。

从第二行开始,下面连续 nn 行,每行有两个字符串(由大写字母、小写字母、下划线、数字、上引号或者逗号组成),分别表示的是这个镇员和他的直属上司。特别地,第二行是镇长,他没有直属上司,所以第二行只有一个字符串,表示镇长。数据保证第二个字符串在第一个字符串前出现过。

输出格式

一行一个整数,表示最大的安全值。

3 1
1
2 1
3 2
1
7 3
LDLD
tk_sky LDLD
Jayden_deng LDLD
only_xiaohuang tk_sky
Muddled_xiaopan tk_sky
Inkn only_xiaohuang
ipdjkl only_xiaohuang
8

提示

样例解释

第二个样例:(图片有可能会挂,请耐心等待一会哦 qwq)




由于出题人过懒,移动子节点的情况就未列举。请自行 hack 自己。(滑稽)

数据范围

记下列两种特殊情况:

  1. 保证字符串长度为 11
  2. 树退化成一条链。
    对于所有的数据,保证 kkint 范围内,字符串长度不超过 10610^6n,kn,k 均为正整数。