AT_tenka1_2014_qualB_e カラオケランキング

[problemUrl]: https://atcoder.jp/contests/tenka1-2014-qualb/tasks/tenka1_2014_qualB_e トモアキ君は天下一王国のアイドルが大好きで、カラオケでは天下一王国のアイドルの曲しか歌いません。 天下一王国のアイドルの曲は合計で $ 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 $ 桁与えられる。

トモアキ君の最適戦略を意味する $ 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 $ つを出力せよ。 出力の最後に改行を入れること。

### 部分点 - $ L\ =\ 1 $ かつ $ 1\ ≦\ N,M\ ≦\ 2,000 $ を満たす全てのテストケースに正解した場合、部分点として $ 30 $ 点が与えられる。 - $ 1\ ≦\ L,N,M\ ≦\ 2,000 $ を満たす全てのテストケースに正解した場合、部分点として上記とは別に $ 30 $ 点が与えられる。 ### Sample Explanation 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... $ 点となり、これがトモアキ君が得られる最高点です。 ### Sample Explanation 2 答えとなる出力は複数存在しますが、どれを出力しても問題ありません。 曲 $ 1 $ 、曲 $ 2 $ 共に、他の人が歌い終わった後に $ 1 $ 回ずつ歌えば、それぞれ補正込みの点数は $ 95.000 $ 点になります。