/ TYWZ / 题库 /

2019.2.11 Problem B - letter

2019.2.11 Problem B - letter

题目描述

某个字符集中有\(n\)种字母,第\(i\)种字母的价值为\(v_i\)/个,\(i = 1 \cdots n\)。注意\(v_i\)可能是负数。
现要构造一个任意长度的字符串\(s\),要求第\(i\)种字母的出现次数不得超过\(num_i\)。定义该串的价值为\(\sum_{i=1}^{\lvert s \rvert} {i \times v_{s_i}}\),即\(k \times \)第\(k\)位字符的价值,然后对\(k=1 \cdots \lvert s \rvert\)求和。(其中符号\(\lvert s \rvert\)表示字符串\(s\)的长度)
求所有可以构造出的串中,最大的价值是多少。注意由于这个串可以是空的,所以价值一定不会小于0。

输入格式

第一行一个整数\(n\),表示字母的种类数;
接下来\(n\)行,每行两个正数\(v_i,num_i\),含义见上。

输出格式

一个整数,表示最大的串的价值。

样例

输入

3
-5 3
2 1
1 1

输出

5

数据规模、时空限制

对于30%的数据,\(n \leq 10\);
对于另外20%的数据,\(v_i \geq 0\);
对于100%的数据,\(n \leq 100000, \quad |v_i| \leq 100, \quad num_i \leq 10\)。
时间限制1s,空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人:于剑

信息

难度
8
分类
贪心 点击显示
标签
(无)
递交数
158
已通过
21
通过率
13%
上传者

相关