[編程|1000分] 可樂(lè)
時(shí)間限制：C/C++ 1秒腹暖，其他語(yǔ)言 2秒
空間限制：C/C++ 262144K，其他語(yǔ)言 524288K
64bit IO Format: %lld
題目描述
小美和小團(tuán)最近沉迷可樂(lè)愿阐∥⒎可供TA們選擇的可樂(lè)共有k種，比如可口可樂(lè)缨历、零度可樂(lè)等等，每種可樂(lè)會(huì)帶給小美和小團(tuán)不同的快樂(lè)程度糙麦。
TA們一共要買n瓶可樂(lè)辛孵，每種可樂(lè)可以買無(wú)限多瓶，小美會(huì)隨機(jī)挑選其中的m瓶喝赡磅，剩下的n-m瓶小團(tuán)喝魄缚。
請(qǐng)問(wèn)應(yīng)該如何購(gòu)買可樂(lè)，使得小美和小團(tuán)得到的快樂(lè)程度的和的期望值最大焚廊？
現(xiàn)在請(qǐng)求出購(gòu)買可樂(lè)的方案冶匹。
輸入描述:
第一行三個(gè)整數(shù)n，m咆瘟，k分別表示要買的可樂(lè)數(shù)嚼隘、小美喝的可樂(lè)數(shù)以及可供選擇的可樂(lè)種數(shù)。
接下來(lái)k行袒餐，每行兩個(gè)整數(shù)a飞蛹，b分別表示某種可樂(lè)分別給予小美和小團(tuán)的快樂(lè)程度。
對(duì)于所有數(shù)據(jù)灸眼，1 <= n <= 10,000, 0 <= m <= n, 1 <= k <= 10,000, -10,000 <= a, b <= 10,000
輸出描述:
一行k個(gè)整數(shù)卧檐，第i個(gè)整數(shù)表示購(gòu)買第i種可樂(lè)的數(shù)目。
如果有多解焰宣，請(qǐng)輸出字典序最小的那個(gè)霉囚。
對(duì)于兩個(gè)序列 a1, a2, ..., ak, b1, b2, ..., bk，a的字典序小于b匕积，當(dāng)且僅當(dāng)存在一個(gè)位置i <= k滿足：
ai < bi且對(duì)于所有的位置 j < i盈罐，aj = bj逻澳；
示例1
輸入
2 1 2
1 2
3 1
輸出
0 2
說(shuō)明
一共有三種購(gòu)買方案：
- 買2瓶第一類可樂(lè)，小美和小團(tuán)各喝一瓶暖呕，期望得到的快樂(lè)程度和為1+2=3斜做；
- 買1瓶第一類可樂(lè)和1瓶第二類可樂(lè)，小美和小團(tuán)各有二分之一的概率喝到第一類可樂(lè)湾揽，另有二分之一的概率喝到第二類可樂(lè)瓤逼，期望得到的快樂(lè)程度和為10.5+30.5+20.5+10.5=3.5；
- 買2瓶第二類可樂(lè)库物，小美和小團(tuán)各喝一瓶霸旗，期望得到的快樂(lè)程度和為3+1=4。
