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

현대모비스는 연간 매출 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$는 $i$번째 부품의 크기, $v_i$는 무게를 나타낸다. ($1 \le u_i \le A$, $1 \le v_i \le B$)

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

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