실행 시간 제한 | 메모리 제한 |
---|---|
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을 출력해 주세요.
3 6 3 3 1
5
출처: USACO 2011 November Contest, Silver Division Problem 3. Tile Exchanging