gistfile1.hs

import Control.Monad (foldM)

split s = let prefix = takeWhile (/= ' ') s in (prefix, drop (1 + length prefix) s)

main = do
        nm <- getLine
        let (sn, sm) = split nm
        let (n, m) = (read sn, read sm)
        let step songs index = do
                line <- getLine
                let (frequency, name) = split line
                let quality = read frequency * index
                let song = (quality, name)
                let (better, worse) = span ((>= quality) . fst) songs
                return $ take m $ better ++ [song] ++ worse
        songs <- foldM step [] [1..n]
        sequence_ $ fmap (putStrLn . snd) songs