TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5408
  • 题目
  • P5408【欢乐的痛苦赛】代购的生意
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    问题描述

    nodgd正在进行代购的生意,过程就是在A国购买一些东西,回到C国之后再卖给别人。

    现在有 \(n\) 种商品有代购需求,编号从 $1$ 到 \(n\) 。第 \(i\) 种商品在A国的售价是 $a_i $ ,回到C国后最多可以卖出 $b_i $ 件,每件的净利润是 $c_i $ (不用考虑汇率影响)。

    众所周知,回国时要过海关。如果nodgd携带的所有商品在A国的总售价超过 \(m\) ,就认为nodgd的行为属于走私犯罪,会把nodgd关进小黑屋。因此,nodgd不得不放弃一部分代购生意,以免被关进小黑屋。

    那么问题来了,nodgd应该如何规划每种商品代购的数量,才能获得最大净利润呢?

    nodgd觉得这个问题太简单,于是补充提问,获得这个最大净利润有多少种不同的代购方案?两种代购方案只要任何一种商品的代购数量不同,就认为是不同的方案。方案数可能很大,只需要计算出答案 \(\bmod 100,000,007\) 之后的值。

    输入格式

    输入共 \(n+1\) 行。

    第一行有两个整数 \(n,m​\) ,分别表示可以代购的商品种类数、海关的限制。

    接下来 \(n​\) 行,每行三个整数 \(a_i,b_i,c_i ​\) ,分别表示商品在A国的售价、回到C国后最多可以卖出多少件、每件的净利润。

    输出格式

    输出共两行。

    第一行有一个整数,表示nodgd能够获取的最大净利润。

    第二行有一个整数,表示获取最大净利润的代购方案数 $\bmod 100,000,007 $ 后的结果。

    样例输入

    2 8
    4 1 2
    3 2 2

    样例输出

    4
    2

    提示

    输入输出样例1说明

    两种商品分别代购 $1,1$ 个,或者 $0,2$ 个,获得的净利润最大。所以最大净利润为 $4$ ,共有 $2$ 种获得最大净利润的方案。

    数据规模与约定

    前 $10\% $ 的数据, $n=1 $ ;

    接下来 $30\%$ 的数据, $b_i=1 $ ;

    前 $70\%$ 的数据, \(m\leq 500\)

    所有测试数据, $1\leq m\leq 50000$,其他数都在 $1$ 到 $100$ 之间。


    来源  感谢nodgd命题