노래

존 도우(John Doe)는 유명한 DJ이며, 그래서 테이프에 노래를 배치하는 순서를 최적화하는 문제를 안고 있습니다. 주어진 테이프와 그 테이프에 담길 각 노래에 대해, 존은 노래의 길이와 재생 빈도를 알고 있습니다. 그의 과제는 기대 접근 시간을 최소화하는 순서로 노래들을 테이프에 녹음하는 것입니다.

노래들이 $S_{s(1)}, \dots, S_{s(n)}$ 순서로 녹음될 때, 최소화해야 하는 값은 다음과 같습니다.

$$\sum_{i=1}^{n} f_{s(i)} \sum_{j=1}^{i} l_{s(j)}$$

여기서 $f_{s(i)}$는 $i$번째에 놓인 노래의 재생 빈도이고, $l_{s(j)}$는 $j$번째에 놓인 노래의 길이입니다. (안쪽 합은 $i$번째 노래에 도달하는 데 걸리는 시간으로, 그 노래 자신을 포함하여 앞에 녹음된 노래들의 전체 길이입니다.) 존을 도와줄 수 있나요?

입력은 텍스트 파일에서 읽어들이며 여러 개의 데이터 집합으로 이루어집니다. 각 데이터 집합은 노래의 수 $N$(16비트 정수 범위)으로 시작합니다. 이어서 $N$개의 노래 명세가 오고, 마지막으로 최적화된 테이프에서 어떤 노래 $S$의 위치를 나타내는 수가 주어집니다. 각 노래 명세는 노래 식별자(정수), 노래의 길이(16비트 정수 범위), 그리고 노래의 재생 빈도(부동소수점 수)로 이루어집니다. 입력에서 공백 문자는 자유롭게 나타날 수 있으며, 입력은 항상 올바르고 파일의 끝(EOF)에서 종료됩니다.

각 데이터 집합마다, 기대 접근 시간을 최소화하는 순서에서 요청된 위치에 놓이는 노래의 식별자를 한 줄의 맨 앞에서부터 출력합니다. 두 노래의 길이 대 빈도 비율 $l/f$가 같으면 서로 순서를 바꾸어도 비용이 변하지 않는데, 이 경우 두 노래는 입력에 나타난 순서대로 배치되므로 각 위치의 노래가 유일하게 결정됩니다.