레이싱 전략

Erika Isabella Orav는 FI(Formula Informatics) 레이싱 시리즈의 Celsius MotoSport 팀 드라이버이다. 새 레이스가 곧 열리며 일기예보도 좋다. 팀은 피트 스톱 기술을 꾸준히 연습했지만, 가장 좋은 전략을 찾는 데 도움이 필요하다.

레이스는 $N$개의 랩으로 이루어진다. 팀은 고무 배합이 다른 $M$종류의 타이어를 사용할 수 있다. 배합에 따라 그립(차가 얼마나 빨리 달릴 수 있는지)과 마모(타이어가 얼마나 빨리 닳는지)가 정해진다. 종류별 타이어 개수에는 제한이 없다.

레이스가 시작할 때 고른 타이어는 이미 차에 장착되어 있으므로 피트 스톱은 필요 없다. 레이스 중 운전자는 어느 랩을 마친 뒤에든 피트에 들어가 현재 타이어를 임의의 종류의 새 타이어로 교체할 수 있다. 피트 스톱에는 $K$초가 걸린다.

Celsius MotoSport 팀은 타이어 종류 $i$마다 두 값을 분석했다.

• $P_i$: 이 종류의 타이어로 첫 랩을 도는 데 걸리는 초.
• $W_i$: 이후 각 랩이 직전 랩보다 느려지는 초.

레이스 전체를 가장 짧은 시간에 마치는 피트 스톱 전략을 찾아라.

첫 줄에 공백으로 구분된 세 정수 $M$ ($1 \le M \le 500$), $N$ ($1 \le N \le 200$), $K$ ($1 \le K \le 1\,000$)이 주어진다. 이어지는 $M$개의 줄에는 각각 공백으로 구분된 두 정수 $P_i$ ($1 \le P_i \le 1\,000$)와 $W_i$ ($0 \le W_i \le 1\,000$)가 주어진다. 타이어 종류는 입력 순서대로 $1, \ldots, M$번이다.

첫 줄에 공백으로 구분된 두 정수 $i_0$와 $B$를 출력한다. $i_0$은 출발할 때 장착할 타이어 종류이고, $B$는 피트 스톱 횟수이다. 이어지는 $B$개의 줄에는 피트 스톱마다 두 정수를 출력한다. 첫 번째는 피트에 들어가는 랩 번호($1, \ldots, N$)이고, 두 번째는 새 타이어의 종류이다. 피트 스톱은 시간 순서대로 나열한다. 최적 전략이 여러 개면 그중 아무거나 출력해도 된다.