시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB67116715125.901%

문제

최근 투자 실패로 전세 자금을 날려 먹은 준엽이는 여자친구와 방을 합치기로 했다. 부푼 마음을 가지고 이사를 하던 준엽이는 책장 앞에서 여자친구와 대립 중이다. 바로 깔끔하지 못한 여자친구의 책꽂이 습관 때문이다. 강박증이 심한 준엽이는 책장에 책이 비스듬히 세워지거나 옆으로 넘어지는 것을 원하지 않는다. 

     

준엽이가 좋아하지 않는 책장 상태

준엽이는 ㄱ자 모양 북엔드를 몇 개 구매하여, 책들을 넘어지지 않게 고정하고 싶다. 준엽이는 책들의 위치와 배열에 상관없이, 어떤 책도 넘어지지 않고 양면이 지탱되고 있는 상태를 좋아한다. 당연하겠지만, 강박증이 있는 준엽이는 책들의 순서가 바뀌는 것을 좋아하지 않는다. 즉, 준엽이가 가져온 책들의 순서가 그대로 유지되어야 한다.

                   

북엔드 실물                                                                             준엽이가 좋아하는 책장 상태 

 

신나는 마음으로 북엔드를 구입한 준엽이는 당황했다. 북엔드의 바닥 면이 생각보다 컸던 것이다. 만약 두 개의 북엔드의 바닥 면을 겹쳐 놓으면 한쪽 북엔드가 기울어져서 보기 싫은 상태가 된다. 준엽이를 도와 책장을 깔끔하게 정리해 줄 북엔드의 최소 개수를 구해 주자. 북엔드는 충분히 크고 무거워서 책에 밀려 넘어지지 않는다고 가정한다.

입력

첫 번째 줄에 책의 개수 정수 N (1 ≤ N ≤ 100)과, 책장의 너비 정수 M (1 ≤ M ≤ 300), 북엔드의 바닥 면의 길이 정수 L (1 ≤ L ≤ 300)이 주어진다.

두 번째 줄에 각 책의 너비인 정수 xi (1 ≤ xi ≤ 3)가 왼쪽 책부터 차례대로 N개 주어진다.

출력

첫 번째 줄에 준엽이가 좋아하는 책장 상태를 만드는 데 필요한 최소 북엔드의 개수를 출력한다. 만약 불가능하다면 -1을 출력한다. 

예제 입력 1

2 5 2
1 1

예제 출력 1

1

예제 입력 2

2 4 3
1 1

예제 출력 2

-1

힌트

     책이 비스듬히 세워져 있어 준엽이가 좋아하지 않는 상태