파일 업로드

타일 교환

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

 

현수는 다이소에서 최근에 구입한 정사각형 타일들을 사용하여 바닥을 리모델링하려고 합니다. 하지만 안타깝게도 그는 구매하기 전에 크기를 제대로 측정하지 않았기 때문에 일부 타일을 다른 크기의 새 정사각형 타일로 교환해야 합니다.

현수가 이전에 구입한 N개의 정사각형 타일의 변의 길이는 A_1...A_N 입니다. 그는 이 타일들 중 일부를 교환하여 전체 타일 영역의 합이 정확히 M이 되게 하고 싶습니다. 

현재 다이소에서는 특별한 할인 행사를 진행 중입니다: 변 길이가 A_i인 타일을 변 길이가 B_i인 새로운 타일로 교환하는데 드는 비용은 |A_i-B_i|*|A_i-B_i|입니다. 

하지만 이 행사는 이전에 구입한 타일에만 적용되며, 현수가 다른 타일을 내고 교환을 한 타일을 다시 또 다른 타일로 교환할 수 없습니다(즉, 크기 3인 타일을 크기 2인 타일로 바꾼 다음 크기 1인 타일로 바꿀 수 없습니다.).

타일 영역의 합이 M이 되도록 타일을 교환하는데 필요한 최소 비용을 결정해 주세요. 만약 M의 면적을 얻는 것이 불가능하다면 -1을 출력해 주세요.

💻 입력
  • 첫 번째 줄 : 두 개의 공백으로 구분된 정수, N (1<=N<=10)과 M (1<=M<=10,000).
  • 두 번째 줄..1+N 번째 줄 : 각 줄에서는 입력 정사각형의 한 변 길이를 설명하는 정수 A_1부터 A_N까지 중 하나가 포함됩니다. (1<=A_i<=100).
🖨️ 출력
  • 첫 번째 줄 : 전체 면적이 M 단위가 되도록 타일을 교환하는 최소 비용, 또는 이것이 불가능한 경우 -1.

💻 예제 입력 1
3 6
3
3
1
🖨️ 예제 출력 1
5

출처: USACO 2011 November Contest, Silver Division Problem 3. Tile Exchanging