#P18163. Bus Analysis
Bus Analysis
Bus Analysis
Adam 将乘公交车进行一段很长的旅行。他可以买 20 分钟票,每张 2 PLN;也可以买 75 分钟票,每张 6 PLN。车票可以在任意整数分钟购买,购买时立即生效。例如,9:14:00 购买的 20 分钟票有效至 9:33:59。他可以在已有车票仍然有效时购买新票。
公交车停靠 个车站,第 站的停靠时间为第 分钟。每站都可能有检票员等候。他们上车后立即检查所有乘客,然后在该站下车;这一过程仅需几秒。
旅行开始前,Adam 会获知哪些车站有检票员,然后安排购票,使每次检查时都有有效车票,并使总费用最小。
考虑每站是否有检票员的全部 种安排,分别求出 Adam 的最少费用,再将这些费用相加。输出总和对 取模的结果。
输入格式
第一行一个整数 ,满足 。
第二行 个整数 ,满足 ,且 。
输出格式
输出一个整数,表示费用总和对 取模的结果。
样例 1
输入:
3
1 8 20
输出:
14
没有检票员的安排费用为 0,其余七种安排都只需一张 20 分钟票,总费用为 。
样例 2
输入:
5
25 45 65 85 1000000000
输出:
156
例如,五站都有检票员时,最少费用为 8:在第 25 分钟买一张 75 分钟票,再在第 分钟买一张 20 分钟票。若只有第 25、45 分钟两站有检票员,最少费用为 4,可以在这两站分别买短票,也可以在第 17、26 分钟购买。
车票有效时间按左闭右开区间计算:第 分钟买的 分钟票,覆盖整数分钟 。