A slightly faster zipfsong implementation.

faster_zipfsong.py

from heapq import heappush, heappop


def run():
    album_songs_count, songs_count = raw_input().split()
    album_songs_count = int(album_songs_count) + 1
    songs_count = int(songs_count)

    songs = []
    for i in xrange(1, album_songs_count):
        freq, title = raw_input().split()
        qi = -int(freq) * i
        heappush(songs, (qi, i, title.strip()))

    print '\n'.join([heappop(songs)[2] for _ in xrange(songs_count)])


if __name__ == "__main__":
    run()