24724번 - 현대모비스와 함께하는 부품 관리

현대모비스는 연간 매출 36조 이상의 글로벌 7위 자동차 부품사입니다.

1977년에 설립된 현대모비스는 'Innovation for Humanity, Mobility for Tomorrow'를 비전으로 자율주행, 커넥티비티, 전동화 등 미래 모빌리티 분야를 선도하기 위해 역량을 집중하고 있습니다.

현대모비스는 전동화, 제동, 샤시, 서스펜션, 조향, 에어백, 램프, 전장 등 자동차 핵심부품 개발에 앞장서고 있으며, 특히 센서, ECU 센서 융합, 안전 제어를 위한 소프트웨어 개발 분야에서 뛰어난 전문성을 보유하고 있습니다.

2022년 새 학기를 맞이하면서 현대모비스에서 연세대학교 프로그래밍 동아리 모르고리즘 회원들에게 사내 견학 및 현장 체험 기회를 제공해줬다. 그에 따라서 동아리원들은 현대모비스 본사로 견학을 가게 되었다.

현대모비스는 자동차 부품을 만들고 그 부품들을 여러 그룹으로 나눠서 관리한다. 안전사고를 방지하기 위해서 각 그룹별로 그룹에 속한 부품들의 크기의 합이 $A$를 넘기지 않으면서 무게의 합이 $B$를 넘기지 않게 하려고 한다. 또한, 부품 관리의 효율성을 위해서 그룹의 수를 최소화하려고 한다. 동아리원들의 현장 체험으로 현대모비스는 이러한 "부품 관리 프로그램"을 동아리원에게 만들어보게 하려고 한다. 그리고 현장에 대한 경험이 부족한 동아리원들을 위해서 "부품 관리 프로그램"의 일부로 들어갈 "그룹 분류 프로그램"을 미리 제공한다.

그룹 분류를 하려고 하는 부품의 크기와 무게가 주어졌을 때, "부품 관리 프로그램"을 만들어보자.

첫 번째 줄에 부품 관리 횟수를 나타내는 양의 정수 $T$가 주어진다. ($1 \le T \le 10$)

각 부품 관리에 대한 입력은 다음과 같이 주어진다.

• 첫 번째 줄에는 부품의 개수를 나타내는 양의 정수 $N$이 주어진다. ($1 \le N \le 10\,000$)
• 두 번째 줄에는 각 그룹의 크기 제한과 무게 제한을 나타내는 양의 정수 $A$와 $B$가 주어진다. ($1 \le A, B \le 10^9$)
• 세 번째 줄부터 $N$개의 줄에 걸쳐서 각 부품의 크기와 부품에 대한 정보를 나타내는 양의 정수 $u_i$와 $v_i$가 주어진다. $u_i$와 $v_i$는 각각 $i$번째 부품의 크기와 무게를 나타낸다. ($1 \le u_i \le A$, $1 \le v_i \le B$)

각 부품 관리에 대해서 다음을 출력한다.

• 첫 번째 줄에는 Material Management x를 출력한다. x는 부품 관리 process의 번호를 의미하고, 이는 $1$부터 시작하여 $1$씩 증가한다.
• 두 번째 줄에는 현대모비스에서 개발한 그룹 분류 프로그램의 완료를 나타내는 문구인 Classification ---- End!를 출력한다.