/ 
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
トモアキ君は天下一王国のアイドルが大好きで、カラオケでは天下一王国のアイドルの曲しか歌いません。
天下一王国のアイドルの曲は合計で L 曲カラオケで歌うことができ、それらを曲 1、曲 2、…、曲 Lと呼びます。
トモアキ君が全力で曲 i を歌うと、カラオケの採点で毎回 K_i 点を取ることができます。
トモアキ君は天下一王国のアイドルの曲を侮辱することは決してしないため、毎回全力で歌います。
ランキングは、その月に獲得した、直近 M 回の「補正込みの点数」の和で決まります。
「補正込みの点数」は、採点結果の点数を x 点としたとき、 x + (x - その曲のその時点での平均点) で計算されます。
「その曲のその時点での平均点」とは、その月の、その x 点を取った回以前 (その回を含む) に、その曲が歌われたときの採点結果の点数の平均となります。
トモアキ君は、超人的なプログラミング能力を駆使して、今月に天下一王国のアイドル関係の曲が、どのタイミングで歌われ、どれだけの点数が取られるかを予測しました。
トモアキ君の予測によると、今月の i 番目に天下一王国のアイドルの曲を歌う人は曲 A_i を歌い、S_i 点を取るということです。
今月はまだ始まったばかりで、まだ誰もどの天下一王国のアイドルの曲を歌っていない状態です。
トモアキ君は、好きなタイミングで歌うことができ、また、任意の 2 人が歌う間、および最初に歌う人の前、最後に歌う人の後に何回でも歌うことができます。
トモアキ君は、来月の予測をしていない上、毎回全力で歌うため、今月にちょうど M 回だけ歌い、ランキング上位を目指します。
トモアキ君は、 M 回の補正込みの点数の和を最大化するような最適な戦略を知りたいです。
そこで、トモアキ君の予測が正しいと仮定して、トモアキ君が歌うべきタイミングを求めるプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
L N M K_1 K_2 .. K_L A_1 S_1 A_2 S_2 : A_N S_N
- 1 行目には、天下一王国のアイドルの曲の数を表す整数 L\ (1 ≦ L ≦ 100,000) 、今月トモアキ君以外によって天下一王国のアイドルの曲が歌われる回数を表す整数 N\ (1 ≦ N ≦ 100,000) 、トモアキ君が今月歌う回数を表す整数 M\ (1 ≦ M ≦ 100,000) がスペース区切りで与えられる。
- 2 行目には、トモアキ君が、天下一王国のアイドルの曲を歌った時に獲得可能な点数の情報が、 L 個の数によって、スペース区切りで与えられる。このうち、 i\ (1≦i≦L) 番目の数 K_i\ (68.000 ≦ K_i ≦ 100.000) は、 i 番目の曲でトモアキ君が獲得可能な点数を表す。
- 3 行目から N 行では、トモアキ君以外の人が歌った曲と、その点数のデータが、1 行ずつ与えられる。そのうち i\ (1≦i≦N) 行目では、i番目に歌われた曲の番号を表す整数 A_i\ (1≦A_i≦L) と、その時の点数 S_i\ (68.000 ≦ S_i ≦ 100.000) がスペース区切りで与えられる。
- K_i および S_i は、小数点以下ちょうど 3 桁与えられる。
部分点
- L = 1 かつ 1 ≦ N,M ≦ 2,000 を満たす全てのテストケースに正解した場合、部分点として 30 点が与えられる。
- 1 ≦ L,N,M ≦ 2,000 を満たす全てのテストケースに正解した場合、部分点として上記とは別に 30 点が与えられる。
出力
トモアキ君の最適戦略を意味する M 行を出力せよ。
ここで、i 行目は 2 つのスペース区切りの整数 T_i, B_i を出力し、T_i は i 番目にトモアキ君が歌うタイミングを、B_i は i 番目にトモアキ君が歌う曲を意味する。
この出力は、 0 ≦ T_1 ≦ T_2 ≦ ... ≦ T_M ≦ N でなければならない。
T_i = k というのは、トモアキ君以外で天下一王国のアイドルの曲がちょうど k 回歌われた後に、トモアキ君が i 番目に歌う曲 B_i を歌うことを意味する。
複数の最適戦略がある場合は、最適戦略のうちの任意の 1 つを出力せよ。
出力の最後に改行を入れること。
入力例1
1 5 3 80.000 1 68.000 1 70.000 1 85.000 1 72.000 1 68.000
出力例1
2 1 2 1 5 1
このケースは、曲数が 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 となります。
3 回目に歌うのは、トモアキ君以外で 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
2 2 2 90.000 90.000 1 80.000 2 80.000
出力例2
2 2 2 1
答えとなる出力は複数存在しますが、どれを出力しても問題ありません。
曲 1 、曲 2 共に、他の人が歌い終わった後に 1 回ずつ歌えば、それぞれ補正込みの点数は 95.000 点になります。
入力例3
4 8 9 78.245 74.123 79.254 81.111 1 69.241 2 68.000 3 81.255 4 80.582 4 80.895 3 87.433 2 100.000 1 76.365
出力例3
1 1 1 1 4 4 5 4 5 4 5 4 5 4 5 4 5 4