루미 알고리즘

#1654실버Arborist

PO 2026 학교 예선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Teo has finally landed his dream job; he has started working as an arborist! An important part of an arborist's job is planting trees.

Teo now needs help planting N trees at integer positions along a number line. The number line starts at position 0, and the value increases by 1 for every step to the right (and decreases by 1 to the left).

For all N trees, Teo has already decided exactly which integer positions on the number line they should be planted at. These positions are all positive integers.

Teo is currently at position 0, together with N large tree saplings. To plant the trees, he can do the following:

  • Move one step to the right (increase the position by 1).
  • Move one step to the left (decrease the position by 1).
  • If Teo is at position 0, he can pick up one of the N tree saplings.
  • Plant one of the saplings he is carrying at the position he is currently at.

Each such action takes exactly one second.

Unfortunately, Teo can carry at most K kilograms of trees at a time. Each tree weighs either 20 or 40 kilograms. Once all trees have been planted, Teo must also return to position 0.

Your task is to compute how long it takes for Teo to plant all the trees and then return to position 0, if he works in the fastest possible way.

Input

The first line of input contains N and K (1 ≤ N ≤ 8, 20 ≤ K ≤ 50), the number of trees to be planted and the number of kilograms Teo can carry, respectively.

The second line contains N integers x_1, …, x_N (1 ≤ x_i ≤ 30), the positions where each sapling should be planted.

The third line contains N integers k_1, …, k_N (k_i ∈ {20, 40}, k_i ≤ K), the weight of each sapling in kilograms.

The input thus describes N trees numbered 1 to N, where tree i should be planted at position x_i and weighs k_i kilograms.

Output

Print an integer: the minimum number of seconds Teo needs to plant all the trees and then return to position 0.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
120K = 25
220k_i = 20 for all i.
320All trees should be planted at the same position.
440No additional constraints.

Explanation of Samples

In sample 1 there are two trees. One of the trees weighs 20 kilograms and should be planted at position 1. The other tree weighs 40 kilograms and should be planted at position 2. An optimal solution for Teo is to do the following:

  • Pick up the tree that should be planted at position 1.
  • Go right.
  • Plant the tree that should be planted at position 1.
  • Go left.
  • Pick up the tree that should be planted at position 2.
  • Go right.
  • Go right.
  • Plant the tree that should be planted at position 2.
  • Go left.
  • Go left. He has now returned to position 0 and is thus done.

There are other ways to plant the trees equally fast, but it is not possible to do it in fewer than 10 seconds.

In sample 2, an optimal solution is to first plant the tree at position 9, then the trees at positions 10 and 8 in the same trip, and finally the one at position 7.

예제

예제 1

입력
2 45
1 2
20 40
출력
10

예제 2

입력
4 42
10 9 7 8
20 40 20 20
출력
60

출처 표기

출처: Programmeringsolympiaden 2026년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.