AT_tenka1_2014_qualB_e カラオケランキング

トモアキ君是天下一王国偶像的忠实粉丝，在卡拉OK时只唱他们的歌。该偶像的歌曲共有 $L$ 首，分别编号为曲 $1$ 至曲 $L$。如果トモアキ君全力演唱曲 $i$，他每次都能得到 $K_i$ 分。他绝不会忽视偶像的歌曲，所以每次都会全力以赴。 排行榜是根据本月最近 $M$ 次演唱的“修正分数”总和来决定的。假设得分为 $x$，则“修正分数”计算公式为 $x + (x - \text{当时该曲目的平均分})$。“当时该曲目的平均分”是指在取得分数 $x$ 之前（包括本次）所有演唱该曲目的评分结果的平均值。 トモアキ君利用精湛的编程能力，预测了本月期间其他人演唱天下一王国偶像曲目的情况。据预测，第 $i$ 位演唱者将演唱曲 $A_i$，并获得 $S_i$ 分。本月刚刚开始，还没有人演唱过任何歌曲。トモアキ君可以在任意时间点演唱，包括其他人演唱前后，以及两次演唱之间。他本月将演唱 $M$ 次，以期争取排行榜的高位次。为了实现目标，他希望知道在哪些时机演唱是最佳的，以使得 $M$ 次修正分数之和最大化。请编写程序，根据トモアキ君的预测分析出最优的演唱策略。

输入以如下格式提供： > $L$ $N$ $M$ $K_1$ $K_2$ … $K_L$ $A_1$ $S_1$ $A_2$ $S_2$ … $A_N$ $S_N$ - 第一行的三个整数分别为：歌曲数 $L\ (1 \leq L \leq 100,000)$、除了トモアキ君以外的歌曲演唱次数 $N\ (1 \leq N \leq 100,000)$、トモアキ君本月的演唱次数 $M\ (1 \leq M \leq 100,000)$。 - 第二行包括 $L$ 个浮点数，分别表示トモアキ君演唱每首歌时可得到的分数 $K_i\ (68.000 \leq K_i \leq 100.000)$。 - 随后的 $N$ 行中，每行包括两个整数和一个浮点数，分别表示第 $i$ 人演唱的歌曲编号 $A_i\ (1 \leq A_i \leq L)$ 和得分 $S_i\ (68.000 \leq S_i \leq 100.000)$。$K_i$ 和 $S_i$ 均精确到小数点后三位。

输出 $M$ 行表示トモアキ君的最佳演唱时机，其中第 $i$ 行包含两个空格分隔的整数 $T_i, B_i$。$T_i$ 表示トモアキ君第 $i$ 次演唱的时间点，$B_i$ 表示演唱的歌曲编号。输出需满足 $0 \leq T_1 \leq T_2 \leq \ldots \leq T_M \leq N$。其中，$T_i = k$ 的意思是，トモアキ君在第 $k$ 次别人演唱后进行他的第 $B_i$ 次演唱。若有多种最佳策略，输出任意一种即可。输出最后需有一个换行符。

### 部分分数 - 当 $L = 1$ 且 $1 \leq N, M \leq 2,000$ 时，若所有测试用例答案正确，可得 30 分。 - 当 $1 \leq L, N, M \leq 2,000$ 时，若所有测试用例答案正确，可额外再得 30 分。 ### 样例解释 1 在这个例子中，仅有一首曲目。假如在其他人第 2 次演唱结束后トモアキ君进行第一次演唱，修正分数计算为 $80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000}{3}) = 87.33333...$。接着继续演唱一次，修正分数为 $80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000 + 80.000}{4}) = 85.5$。第三次演唱放在其他人第 5 次演唱结束后，其修正分数为 $80.000 + (80.000 - \frac{68.000 + 70.000 + 80.000 + 80.000 + 85.000 + 72.000 + 68.000 + 80.000}{8}) = 84.625$。这种策略下，トモアキ君的修正分数总和为 $87.33333... + 85.5 + 84.625 = 257.45833...$，达到最高。 ### 样例解释 2 有多种可能的最佳解，例��：在其他人演唱结束后分别选择曲 $1$ 一次和曲 $2$ 一次，修正分数可均达到 $95.000$。 **本翻译由 AI 自动生成**