题目内容

代码运行过程中可能出现栈溢出。给定函数调用关系及每个函数的独立栈大小，判断程序是否存在栈溢出风险。

如程序如下：

A()

{

    B()；

    C()；

}

B()

{

    D();

}

C()

{

    E();

}

其中A、B、C、D、E的为函数。A调用了B、C;B调用了D;C调用了E。如果每个函数独立的栈大小分别为: A为10(不包括B、C的栈大小),B为20，C为5，D为15，E为50。调用过程中最大栈空间为路径为A>C> E,最大栈空间为65(A- > B- > D的路径调用最大栈空间为45)，如果整体系统最大额定栈空间配置为60，则A- >C- > E调用执行时会出现栈溢出异常。

• 函数名为单个大写字母，最多26个函数。
• 调用关系无递归。
• 最大消耗栈空间若等于系统最大额定空间，不会溢出；仅当大于时才会溢出。
• 计算某条调用路径的总栈空间时，为路径上各函数独立栈大小之和。

输入描述

输入包括三个信息：每个函数的独立栈大小、函数调用关系、系统配置的最大栈空间。格式如下：

第一行：数字N，代表有N个函数。

第二行到N+1行：每行表示每个函数名称和栈大小，空格隔开。

第N+2行：数字M，代表下面M行的函数直接调用关系。每行的第一个字母表示调用函数，后面的字母表示被调用函数，并且是按序调用。如ABC表示先A->B，然后A->C（如示例所示）。

最后一行：数字，代表系统配置的最大栈空间。

说明：假设主函数都是从第一个调用关系开始发起调用（数字M之后的第一行中第一个函数可以认为是主函数调用入口），不会从中间某个函数开始调用。

输出描述

输出信息包括：

1. 是否会出现栈溢出。
2. 如果栈溢出，则输出发生栈溢出的调用路径（路径只输出到触发栈溢出的函数）；如果没有栈溢出，则输出最大消耗栈的调用路径（如果存在相同大小的调用路径，输出第一个）。
3. 如果栈溢出，输出发生栈溢出时调用关系的栈大小；如果没有栈溢出，输出最大栈消耗。

三个信息一行打印，中间空格隔开。如果栈溢出，只输出第一次触发栈溢出时的调用关系即可（实际上如果发生了栈溢出，系统也会异常，不会继续产生后续调用了）。

样例1

输入

6
A 20
B 10
C 5
D 15
E 50
F 60
3
ABC
BD
CEF
70

输出

true A-C-E 75

说明
给定输入，第一个调用关系为A BC，则A为入口函数。先执行A-B-D调用，对应占空间为45；当执行到A-C-E时，超过了70，触发了栈溢出。不会再触发函数C调用函数F了，所以输出为A-C-E，对应的栈空间为75。

样例2

输入

6
A 20
B 10
C 5
D 15
E 50
F 60
2
AB
CEF
100

输出

false A-C-F 85

说明
该示例中，最大占空间配置为100，可以调用完所有函数，不会发生栈溢出。最大调用栈调用关系为A-C-F，消耗的最大栈空间为85。