SKKU 나라는 개의 도시로 이루어진 국가이다. 도로는 양방향으로 통행이 가능하며, 2명의 택배 기사가 각각 번 도시와 번 도시에 존재한다. 택배는 반드시 트럭을 이용해 배송해야 하는데, 금전적인 이유로 두 기사는 하나의 트럭을 공유하게 되었다. 트럭은 초기에 번 도시에 위치해 있으며, 크기가 굉장히 작기 때문에 최대 하나의 택배를 실을 수 있다. 각 기사가 배송해야 할 택배에 대한 정보는 아래와 같다.

- 첫 번째 기사는 번 도시에서 무게 의 택배를 픽업하여 번 도시로 배송해야 한다.

- 두 번째 기사는 번 도시에서 무게 의 택배를 픽업하여 번 도시로 배송해야 한다.

- 두 택배의 무게는 가 성립한다.

이때, 도로를 지나가기 위해서는 2가지 조건을 만족해야 한다.

- 도로를 지나가기 위해서는 트럭에 반드시 택배를 싣고 있어야 한다.

- 도로의 내구성은 현재 트럭에 실린 택배의 무게 이상이어야 한다.

초기에 모든 도로의 내구성은 0이며, 택배 기사는 도로를 지나가기 전에 원하는 만큼 내구성을 올릴 수 있다. 도로를 지나갈 당시 트럭에 보유하고 있는 택배의 무게를 라고 할 때, 각 도로를 지나가기 전 비용을 만큼 지불하여 도로의 내구성을 만큼 올릴 수 있다. (단, ) 도로를 지나가게 되면 도로는 만큼 내구성이 감소한다. 두 택배를 배송하기 위한 최소 비용을 구하여라.

#538. 택배 배달 (Easy)

Input

Output

Sample

Input 1

Output 1

Sample

Input 2

Output 2

Time Limit

Memory Limit

Source

#538. 택배 배달 (Easy)

Input

Output

Sample

Input 1

Output 1

Sample

Input 2

Output 2

Time Limit

Memory Limit

Source