题目描述

得到一种药水有两种方法：可以按照魔法书上的指导自己配置，也可以到魔法商店里去 买——那里对于每种药水都有供应，虽然有可能价格很贵。在魔法书上有很多这样的记载： $\red{1 }$份 $\red{A }$药水混合 $\red{1 }$份 $\red{B }$药水就可以得到 $\red{1 }$份 $\red{C }$药水。（至于为什么 $\red{1+1=1，}$因为……这是魔 法世界）好了，现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及 魔法书上所有的配置方法。

现在要问的就是：

$\red{1.}$最少花多少钱可以配制成功这种珍贵的药水；

$\red{2.}$共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为 不同的）。

假定初始时你手中并没有任何可以用的药水。

输入格式

第一行有一个整数 $\red{N，}$表示一共涉及到的药水总数。药水从 $\red{0 \sim N-1}$顺序编号，$\red{0 }$号药水就是 最终要配制的药水。

第二行有 $\red{N }$个整数，分别表示从 $\red{0}$$\red{\sim N-1 }$顺序编号的所有药水在魔法商店的价格（都表示 $\red{1}$ 份的价格）。

第三行开始，每行有 $\red{3 }$个整数 $\red{A}$、$\red{B}$、$\red{C，}$表示 $\red{1 }$份 $\red{A }$药水混合 $\red{1 }$份 $\red{B }$药水就可以得到 $\red{1 }$份 $\red{C }$药水。

注意，某两种特定的药水搭配如果能配成新药水的话，那么结果是唯一的。也就是 说不会出现某两行的 $\red{A}$、$\red{B }$相同但 $\red{C }$不同的情况。 输入以一个空行结束。

输出格式

输出两个用空格隔开的整数，分别表示得到 $\red{0 }$号药水的最小花费以及花费最少的方案的个 数。

样例

输入样例

7
10 5 6 3 2 2 3
1 2 0
4 5 1
3 6 2

输出样例

10 3

提示

样例说明：

最优方案有 $\red{3 }$种，分别是：直接买 $\red{0 }$号药水；买 $\red{4 }$号药水、$\red{5 }$号药水配制成 $\red{1 }$号药水，直接 买 $\red{2 }$号药水，然后配制成 $\red{0 }$号药水；买 $\red{4 }$号药水、$\red{5 }$号药水配制成 $\red{1 }$号药水，买 $\red{3 }$号药水、$\red{6}$ 号药水配制成 $\red{2，}$然后配制成 $\red{0}$。

对于 $\red{100\%}$的数据，$\red{n<=1000}$。