A91381.「AHOI2014」骑士游戏

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

长期的宅男生活中,JYY 又挖掘出了一款 RPG 游戏。在这个游戏中 JYY 会扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。

在这个游戏中,JYY 一共有两种攻击方式,一种是普通攻击,一种是法术攻击。两种攻击方式都会消耗 JYY 一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死,怪兽的尸体可以变出其他一些新的怪兽,注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽;而采用法术攻击则可以彻底将一个怪兽杀死。当然了,一般来说,相比普通攻击,法术攻击会消耗更多的体力值(但由于游戏系统 bug,并不保证这一点)。

游戏世界中一共有 NN 种不同的怪兽,分别由 11NN 编号,现在 11 号怪兽入侵村庄了,JYY 想知道,最少花费多少体力值才能将所有入侵村庄的怪兽全部杀死呢?

输入格式

第一行包含一个整数 NN
接下来 NN 行,每行描述一种怪兽的信息;
其中第 ii 行包含若干个整数,前三个整数为 SiS_iKiK_iRiR_i,表示对于 ii 号怪兽,普通攻击需要消耗 SiS_i 的体力,法术攻击需要消耗 KiK_i 的体力,同时 ii 号怪兽死亡后会产生 RiR_i 个新的怪兽。其后的 RiR_i 个整数分别表示每个新出现的怪兽编号。同一编号的怪兽可以出现多个。

输出格式

输出一行一个整数,表示最少需要的体力值。

输入输出样例

  • 输入#1

    4
    4 27 3 2 3 2
    3 5 1 2
    1 13 2 4 2
    5 6 1 2

    输出#1

    26

说明/提示

对于所有数据,2N2×105, 1Ri,Ri106, 1Ki,Si5×10142 \leq N \leq 2 \times 10^5,\ 1 \leq R_i,\sum R_i \leq 10^6,\ 1 \leq K_i,S_i \leq 5 \times 10^{14}

首页