TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5914
  • Problem
  • P5914【崛起的欢乐赛】白蛇缘起
    Limits : Time Limit : - MS   Memory Limit : 262144 KB
    Description

    她清丽高雅,仙灵柔美,性格坚韧独立、坚贞不渝,在修炼遇劫不得突破时,由此解开了五百年前一段人妖相恋的尘封记忆。

    白蛇的这段记忆是被法术封印的。共有$n$道独立的法术封印,第$i$道法术封印的强度为$a_i$。法术封印的强度会随着时间流逝而衰减,第$i$道法术封印的强度每过$b_i$天会减少$c_i$。法术封印的衰减是瞬发的,第$i$道封印的强度在第$0$到都$b_i-1$天都是$a_i$,在第$b_i$天到第$2b_i-1$天都是$a_i-c_i$,在第$2b_i$到第$3b_i-1$天都是$a_i-2c_i$,以此类推,直到衰减到$0$为止。封印强度衰减到$0$表示这道封印自动解除了。

    白蛇和青蛇都在努力的解除这些封印。白蛇可以解除至多$p$道封印,青蛇可以解除强度总和不超过$q$的若干道封印。但是,这样的操作白蛇和青蛇至多各施展一次,那么,白蛇至少需要等待多少天,才能解除所有封印?

    Input Format

    第一行三个整数$n,p,q$,表示封印总条数、白蛇能够解除的封印条数、青蛇能够解除的封印强度总和上限。

    接下来$n$行,每行三个整数$a_i,b_i,c_i$,表示第$i$条封印的初始强度和衰减规律。

    Output Format

    输出一行,一个整数,表示至少要等待到哪天,才能解除所有的封印。

    Sample Input 1

    5 1 3
    100 100 1
    10 1 1
    10 2 5
    10 3 5
    2 6 6 

    Sample Output 1

    7

    Sample Input 2

    1 0 0
    1000000000 1000000000 1

    Sample Output 2

    1000000000000000000

    Sample Input 3

    2 1 1
    1000000000 1000000000 1
    100000000 343896 12687523

    Sample Output 3

    2751168

    Hint

    样例说明1

    共有$5$条封印,白蛇可以解除$1$条封印,青蛇可以解除强度总和不超过$3$的若干条封印。在第$7$天,每条封印的剩余强度分别为$100,3,0,0,0$。此时白蛇解除第$1$道封印,青蛇解除第$2$道封印,则所有封印都被解除。

    样例说明2

    白蛇和青蛇都不能进行任何操作,只能等待封印自动解除。

    数据规模与约定

    对于30%的数据,\(n\le500\)
    对于另外30%的数据,所有的封印都会在$500$天内自动衰减到$0$;
    对于100%的数据,$1\le n\le 50000,\ 0\le p\le n,\ 0\le q\le 10^{9}$,其他数据都是正整数且不超过$10^9$。


    Source  感谢nodgd命题