페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10430

압력 조절 5s 1024MB

문제

당신의 주유소에 있는 공기 펌프 줄이 너무 길어지고 있다! 당신은 손님들이 타이어, 스포츠 공, 거대한 퍼레이드 풍선 동물, 그 외 다양한 물건에 공기를 더 빨리 주입할 수 있도록 과정을 최적화하고 싶다.

이 펌프는 자동이다. 당신은 목표 압력을 특정 파스칼(pascal) 값으로 설정한 뒤, 펌프를 공기를 넣을 물건에 연결하면 그 정확한 압력까지 자동으로 공기를 주입한다. 펌프에는 버튼이 두 개뿐인데, 위(up) 버튼과 아래(down) 버튼이다. 각 버튼은 목표 압력을 정확히 1파스칼씩 올리거나 내린다.

Image of air pump and soccer ball.

손님이 \mathbf{N}명 줄을 서 있으며, 각 손님은 펌프로 공기를 넣어야 하는 물건을 정확히 \mathbf{P}개씩 가져온다. 당신은 각 물건의 목표 압력을 알고 있다. 당신은 한 손님이 가져온 물건들을 어떤 순서로든 처리할 수 있지만, 손님의 순서는 바꿀 수 없다. 즉 i번째 손님의 물건들을 모두 처리하기 전에는 (i+1)번째 손님의 어떤 물건도 처리할 수 없다. 두 물건을 연달아 처리할 때 목표 압력이 다르면, 펌프의 버튼을 눌러 목표 압력을 조정해야 한다.

펌프의 초기 목표 압력은 0파스칼이며, 모든 손님의 모든 물건을 처리한 뒤에는 어떤 값으로든 남겨도 된다. 각 손님에 대해 물건 처리 순서를 최적으로 선택한다면, 필요한 버튼 누름 횟수의 최소는 얼마인가?


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 정수 두 개 \mathbf{N}, \mathbf{P}가 주어진 한 줄로 시작한다. 이는 각각 손님의 수와 각 손님이 가져오는 물건의 수이다. 그 다음 \mathbf{N}줄이 이어진다. 이 중 i번째 줄에는 \mathbf{P}개의 정수 \mathbf{X_{i,1}}, \mathbf{X_{i,2}}, \dots, \mathbf{X_{i,P}}가 주어진다. 이는 i번째 손님이 가져온 j번째 물건의 목표 압력이 \mathbf{X_{i,j}}파스칼임을 의미한다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 모든 물건을 지정된 압력으로 부풀리기 위해 필요한 버튼 누름 횟수의 최소값이다.


예제 

2
3 3
30 10 40
20 50 60
60 60 50
5 2
1 1000000000
500000000 1000000000
1 1000000000
500000000 1
1 1000000000
Case #1: 110
Case #2: 4999999996
샘플 케이스 #1에서 펌프를 사용하는 최적 방법은 다음과 같다: 위로 10번 눌러 펌프를 10으로 맞춘 뒤, 고객 1의 10파스칼 제품을 펌프한다. 위로 30번 눌러 펌프를 40으로 맞춘 뒤, 고객 1의 40파스칼 제품을 펌프한다. 아래로 10번 눌러 펌프를 30으로 맞춘 뒤, 고객 1의 30파스칼 제품을 펌프한다. 아래로 10번 눌러 펌프를 20으로 맞춘 뒤, 고객 2의 20파스칼 제품을 펌프한다. 위로 30번 눌러 펌프를 50으로 맞춘 뒤, 고객 2의 50파스칼 제품을 펌프한다. 위로 10번 눌러 펌프를 60으로 맞춘 뒤, 고객 2의 60파스칼 제품과 고객 3의 60파스칼 제품 두 개를 펌프한다. 마지막으로 아래로 10번 눌러 펌프를 50으로 맞춘 뒤, 고객 3의 50파스칼 제품을 펌프한다. 총 버튼 누름 횟수는 110번이다. 샘플 케이스 #2에서는 답이 2^{32}보다 클 수 있음을 유의하라.

출처

GCJ 2022r1b B

로그인해야 코드를 작성할 수 있어요.