[編程|1000分] 可樂
時間限制：C/C++ 1秒，其他語言 2秒
空間限制：C/C++ 262144K，其他語言 524288K
64bit IO Format: %lld
題目描述
小美和小團(tuán)最近沉迷可樂?？晒㏕A們選擇的可樂共有k種，比如可口可樂、零度可樂等等，每種可樂會帶給小美和小團(tuán)不同的快樂程度。
TA們一共要買n瓶可樂，每種可樂可以買無限多瓶，小美會隨機挑選其中的m瓶喝，剩下的n-m瓶小團(tuán)喝。
請問應(yīng)該如何購買可樂，使得小美和小團(tuán)得到的快樂程度的和的期望值最大？
現(xiàn)在請求出購買可樂的方案。
輸入描述:
第一行三個整數(shù)n，m，k分別表示要買的可樂數(shù)、小美喝的可樂數(shù)以及可供選擇的可樂種數(shù)。
接下來k行，每行兩個整數(shù)a，b分別表示某種可樂分別給予小美和小團(tuán)的快樂程度。
對于所有數(shù)據(jù)，1 <= n <= 10,000, 0 <= m <= n, 1 <= k <= 10,000, -10,000 <= a, b <= 10,000
輸出描述:
一行k個整數(shù)，第i個整數(shù)表示購買第i種可樂的數(shù)目。
如果有多解，請輸出字典序最小的那個。
對于兩個序列 a1, a2, ..., ak, b1, b2, ..., bk，a的字典序小于b，當(dāng)且僅當(dāng)存在一個位置i <= k滿足：
ai < bi且對于所有的位置 j < i，aj = bj；
示例1
輸入
2 1 2
1 2
3 1
輸出
0 2
說明
一共有三種購買方案：

1. 買2瓶第一類可樂，小美和小團(tuán)各喝一瓶，期望得到的快樂程度和為1+2=3；
2. 買1瓶第一類可樂和1瓶第二類可樂，小美和小團(tuán)各有二分之一的概率喝到第一類可樂，另有二分之一的概率喝到第二類可樂，期望得到的快樂程度和為10.5+30.5+20.5+10.5=3.5；
3. 買2瓶第二類可樂，小美和小團(tuán)各喝一瓶，期望得到的快樂程度和為3+1=4。