24395번 - 명진이의 신년계획

카오스 동아리 사람들은 모두 코딩에 미쳐있기 때문에 주기적으로 약을 처방받는다. 동아리의 회장 명진이는 새해를 맞아 이들 모두를 치료하고자 한다.

그들이 걸린 질병은 총 M종류이며 각 질병은 0 이상, 100 이하의 위험도를 지닌다. 회원들은 걸린 질병에 따라 특정 개수의 빨강, 파랑 알약을 처방받는다.

• 처방받는 알약의 수와 위험도가 모두 같은 서로 다른 질병이 존재할 수 있다.
• 하나의 질병에 대해 여러 번 처방받을 수 없다.
• 처방받는 알약의 수는 종류별 50개 이하이며 2종류를 합해 최소 1개 이상이다.

명진이는 신년계획에 따라 학생들의 위험군을 계산해 치료 순서 리스트를 작성하고자 한다.

• 위험군은 해당 학생이 지닐 수 있는 질병들의 위험도 합계의 최대치로 정해진다.
• 리스트는 저위험군 학생부터 나열되며, 위험군이 같을 경우 번호가 앞선 학생이 먼저 나온다.
• 만약 학생이 지닌 알약이 어떠한 처방으로도 만들 수 없는 경우, 해당 학생은 미친 척하는 정상인으로 위험군이 0이다.

N명의 학생이 처방받은 빨강, 파랑 알약의 수가 주어졌을 때, 명진이를 도와 치료 순서 리스트를 작성해보자.

첫째 줄에 N (1 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100)이 공백을 두고 주어진다.

둘째 줄부터 M개의 줄에 걸쳐 M개의 질병에 처방할 빨강, 파랑 알약의 수 R_i , B_i (0 ≤ R_i , B_i ≤ 50, R_i + B_i ≥ 1)와 위험도 D_i (0 ≤ D_i ≤ 100)가 공백을 두고 주어진다.

M+2번째 줄부터 N 개의 줄에 걸쳐 N 명의 학생이 처방받은 빨강, 파랑 알약의 수 R'_i , B'_i (0 ≤ R'_i , B'_i ≤ 50, R'_i + B'_i  ≥ 1)가 공백을 두고 주어진다.

N개의 줄에 걸쳐 학생 번호와 위험군을 빈칸을 두고 리스트 순서대로 출력한다.