题面描述

在程序运行过程中，函数调用可能导致栈溢出。给定函数的栈大小和调用关系，判断程序是否会发生栈溢出，并输出相关信息，包括是否溢出、触发溢出的调用路径（如果有）、以及栈的最大消耗。如果没有溢出，则输出最大栈消耗的调用路径。输入包括函数数量、每个函数的栈大小、调用关系和系统最大栈空间，输出需提供三项信息，确保正确识别栈的使用情况。

思路

简化来说，这个问题本质上是一个有向无环图（DAG）中的路径最大权值问题，主要关注的是如何判断路径的栈消耗是否超过系统允许的最大空间。

1. 图结构与路径搜索：
   • 这个问题可以看作是从入口函数出发的一种路径搜索问题，其中每条路径代表一个调用链。

题目内容

代码运行过程，经常会出现栈溢出情况，现给定函数调用关系和每个函数的栈大小，判断该程序是否存在栈溢出的风险。

如程序如下：

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$调用执行时会出现栈溢出异常。

说明

1.函数名称为单个大写字母,最大不超过$26$个函数

2.调用栈为正整数;

3.调用关系不会出现递归调用

4.最大消耗的栈空间等于系统设定的最大空间，不会发生溢出。只有大于系统最大空间，才发生溢出。

输入描述

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

第一行:数字$N$，代表有$N$个函数，

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

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

最后一行:数字$K$，代表系统配置的最大栈空间

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

输出描述

输出信息包括:

1.是否会出现栈溢出，

2.如果栈溢出，则输出发生栈溢出的调用路径(路径只输出到触发栈溢出的函数);如果没有栈溢出，则输出最大消耗栈的调用路径(如果存在相同大小的调用路径，输出第一个)

3.如果栈溢出，输出发生栈溢出时调用关系的栈大小，如果没有栈溢 出，输出最大栈消耗

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

样例1

输入

6
A 20
B 10
C 5
D 15
E 50
F 60
3
A B C
B D 
C E F 
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
3 
A B C
B D
C E F
100

输出

false A-C-F 85

说明

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