P1222 - 税收与补贴问题【NOIP 2000 普及组 T2】
题目背景
每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数）
对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）
题目描述
你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。
- 总利润 $=$ 单位商品利润 $\times$ 销量
- 单位商品利润 $=$ 单位商品价格 $-$ 单位商品成本（减去税金 或者 加上补贴）
输入格式
输入的第一行为政府对某种商品的预期价；
第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销售量；
接下来若干行，每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行 -1 -1 表示所有已知价位及对应的销量输入完毕；
输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。
输出格式
输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。
如在政府预期价上不能得到最大总利润，则输出 NO SOLUTION。
输入输出样例 #1
输入 #1
31
28 130
30 120
31 110
-1 -1
15
输出 #1
4
说明/提示
数据范围及约定
保证输入的所有数字均小于 $10^5$。
测试点数目
共4个测试点，每个测试点25分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：128MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：P1222.in，输出文件名为：P1222.out