당신은 이불 N개를 새로 구매했다. i번째 이불은 si 만큼의 따뜻함을 갖는다. 당신은 앞으로 M일동안의 일기 예보에서 j번째 날에는 dj 만큼의 따뜻함이 필요하다는 것을 알게 되었다. 따뜻함은 필요한 양보다 부족해도 너무 많아도 불쾌하기 때문에, j번째 날에 덮은 이불들의 따뜻함의 총합과 j번째 날에 필요한 따뜻함 dj 의 차의 절댓값을 j번째 날에 받는 불쾌함이라고 하자. 당신은 M일동안 받는 불쾌함의 총합을 최소화하려고 한다.
한편, 당신의 방에는 이불을 보관할 수 있는 수납장과 침대가 있다. 아쉽게도 수납장 이외에는 이불을 보관할 수 있는 공간이 없기 때문에 쓰지 않는 이불은 전부 수납장에 쌓아서 보관해야 한다. 이 때, 침대에 이불을 한 개 더 덮기 위해서는 수납장의 맨 위에 있는 이불을 꺼내 침대의 맨 위에 놓아야 한다. 반대로, 침대 위의 이불을 한 개 빼기 위해서는 침대의 맨 위에 있는 이불을 수납장의 맨 위에 넣어야 한다. 또한, 하루동안 이동하는 이불의 개수에는 제한이 없지만, 한 번에 한 개의 이불만 움직일 수 있다.
당신은 지금부터 사온 이불들을 수납장에 쌓아서 보관하려고 한다. 쌓는 순서를 정해서 이불을 보관한 후에는 더 이상 쌓은 이불들의 순서를 바꿀 수 없다. 적절하게 이불의 쌓는 순서를 정해 수납장에 보관하고, 보관한 이불들을 적절하게 넣고 꺼내서 M일동안 지낼 때, M일동안 받는 불쾌함의 총합의 최솟값을 구하여라. 이 때, 한 번도 사용하지 않는 이불이 있어도 되고, 이불을 하나도 덮지 않는 날이 있어도 된다.
예를 들어, 예제 1번의 5번째 테스트 케이스에서 이불 4개의 따뜻함은 각각 3, 5, 2, 1이고, 3일동안 필요한 따뜻함은 각각 10, 4, 7이다. 이불들을 위에서부터 따뜻함이 5, 2, 3, 1이 되게끔 보관하고, 1일째는 이불을 3번 꺼내서 |10 - (5 + 2 + 3)| = 0, 2일째는 이불을 2번 넣어서 |4 - 5| = 1, 3일째는 이불을 1번 꺼내서 |7 - (5 + 2)| = 0 으로 지낸다면, 3일동안 받는 불쾌함의 총합은 0 + 1 + 0 = 1 이 된다.
ㅤ
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.
첫번째 줄에는 새로 산 이불의 개수인 N과 지내야 하는 기간 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 15, 1≤ M ≤ 100)
두번째 줄에는 N개의 정수 s1, s2, ..., sN 이 공백으로 구분되어 주어지며, si 는 i번째 이불이 갖는 따뜻함을 나타낸다. (1 ≤ si, ≤ 1,000,000)
세번째 줄에는 M개의 정수 d1, d2, ..., dM 이 공백으로 구분되어 주어지며, dj 는 j번째 날에 필요한 따뜻함을 나타낸다. (1 ≤ dj ≤ 1,000,000)
입력의 끝에는 두 개의 0이 주어진다. 이 입력이 들어오면 프로그램을 종료해야 한다.
ㅤ
출력
각 테스트 케이스에 대해, M일동안 받는 불쾌함의 총합의 최솟값을 한 줄에 하나씩 출력한다.
cinador 3년 전 1
문제
당신은 이불 N개를 새로 구매했다. i번째 이불은 si 만큼의 따뜻함을 갖는다. 당신은 앞으로 M일동안의 일기 예보에서 j번째 날에는 dj 만큼의 따뜻함이 필요하다는 것을 알게 되었다. 따뜻함은 필요한 양보다 부족해도 너무 많아도 불쾌하기 때문에, j번째 날에 덮은 이불들의 따뜻함의 총합과 j번째 날에 필요한 따뜻함 dj 의 차의 절댓값을 j번째 날에 받는 불쾌함이라고 하자. 당신은 M일동안 받는 불쾌함의 총합을 최소화하려고 한다.
한편, 당신의 방에는 이불을 보관할 수 있는 수납장과 침대가 있다. 아쉽게도 수납장 이외에는 이불을 보관할 수 있는 공간이 없기 때문에 쓰지 않는 이불은 전부 수납장에 쌓아서 보관해야 한다. 이 때, 침대에 이불을 한 개 더 덮기 위해서는 수납장의 맨 위에 있는 이불을 꺼내 침대의 맨 위에 놓아야 한다. 반대로, 침대 위의 이불을 한 개 빼기 위해서는 침대의 맨 위에 있는 이불을 수납장의 맨 위에 넣어야 한다. 또한, 하루동안 이동하는 이불의 개수에는 제한이 없지만, 한 번에 한 개의 이불만 움직일 수 있다.
당신은 지금부터 사온 이불들을 수납장에 쌓아서 보관하려고 한다. 쌓는 순서를 정해서 이불을 보관한 후에는 더 이상 쌓은 이불들의 순서를 바꿀 수 없다. 적절하게 이불의 쌓는 순서를 정해 수납장에 보관하고, 보관한 이불들을 적절하게 넣고 꺼내서 M일동안 지낼 때, M일동안 받는 불쾌함의 총합의 최솟값을 구하여라. 이 때, 한 번도 사용하지 않는 이불이 있어도 되고, 이불을 하나도 덮지 않는 날이 있어도 된다.
예를 들어, 예제 1번의 5번째 테스트 케이스에서 이불 4개의 따뜻함은 각각 3, 5, 2, 1이고, 3일동안 필요한 따뜻함은 각각 10, 4, 7이다. 이불들을 위에서부터 따뜻함이 5, 2, 3, 1이 되게끔 보관하고, 1일째는 이불을 3번 꺼내서 |10 - (5 + 2 + 3)| = 0, 2일째는 이불을 2번 넣어서 |4 - 5| = 1, 3일째는 이불을 1번 꺼내서 |7 - (5 + 2)| = 0 으로 지낸다면, 3일동안 받는 불쾌함의 총합은 0 + 1 + 0 = 1 이 된다.
ㅤ
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.
첫번째 줄에는 새로 산 이불의 개수인 N과 지내야 하는 기간 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 15, 1≤ M ≤ 100)
두번째 줄에는 N개의 정수 s1, s2, ..., sN 이 공백으로 구분되어 주어지며, si 는 i번째 이불이 갖는 따뜻함을 나타낸다. (1 ≤ si, ≤ 1,000,000)
세번째 줄에는 M개의 정수 d1, d2, ..., dM 이 공백으로 구분되어 주어지며, dj 는 j번째 날에 필요한 따뜻함을 나타낸다. (1 ≤ dj ≤ 1,000,000)
입력의 끝에는 두 개의 0이 주어진다. 이 입력이 들어오면 프로그램을 종료해야 한다.
ㅤ
출력
각 테스트 케이스에 대해, M일동안 받는 불쾌함의 총합의 최솟값을 한 줄에 하나씩 출력한다.