问题 H: 坐地铁!(Hard Version)

问题 H: 坐地铁!(Hard Version)

时间限制: 2 Sec  内存限制: 128 MB
提交: 181  解决: 35
[状态] [讨论版] [提交] [命题人:]
题目描述

请先阅读 "坐地铁!(Easy Version)" 再来作答此题!

是该沙漠同学打算在广州游玩 3 天,他已经规划好 3 天的路线了!为了环(sheng)保(qian),他还是选择搭乘地铁出行

所以乘坐地铁购票的时候有以下几种选择:

  • 3 天所有行程购买均单程票

  • 其中任意 1 或 2 天购买相应张数一日票,剩余 2 或 1 天购买单程票

  • 购买一张三日票

是该沙漠同学不会算数,但是他又想选择一种最省钱的方案,这复杂的计算可把他给绕晕了捏

为了简化问题,我们规定单日票次日 0 点自动失效,第二天不可继续使用

计费规则同 "坐地铁!(Easy Version)" ,故本题不再赘述


输入

第一行输入一个整数 n ( 1 ≤ n ≤ 105 ) ,代表线路上的站点数

第二行输入 n - 1 个实数 a1, a2, a3, ..., an-1 ( ai > 0 )ai 代表区间 i 到 i+1 的距离(其中 i 代表站点编号,单位为公里)

第三行输入三个整数 t1, t2, t3 ( t1, t2, t3 ≥ 0t+ t+ t3 ≤ 10) ,分别代表是该沙漠同学每天要搭乘几次地铁

接下来 t1 行,每行两个整数 x, y ( 1 ≤ x, y ≤ n ) ,分别代表是该沙漠同学第 1 天某次行程起点和终点的站点编号

接下来 t2 行,每行两个整数 x, y ( 1 ≤ x, y ≤ n ) ,分别代表是该沙漠同学第 2 天某次行程起点和终点的站点编号

接下来 t3 行,每行两个整数 x, y ( 1 ≤ x, y ≤ n ) ,分别代表是该沙漠同学第 3 天某次行程起点和终点的站点编号

所有站点编号均不包含前导 0

输出

如果是该沙漠同学三天都没出门(即三天都没有行程),请输出 "Lazy, SkySummer!" 3 遍(每次一行,不含引号)

否则输出一行一个整数 p,即是该沙漠同学这 3 天搭乘地铁的最低车票支出

样例输入 Copy
5
1.2 1.2 1.2 1.2
1 1 1
1 2
2 3
3 4
样例输出 Copy
6
提示

请注意输入格式!

保证 

保证全部行程的单程票票价总和不超过 1010