짐 싸기

야영을 떠날 때가 됐다. 야영에는 이런저런 물건이 필요하고 그 물건을 직접 들고 다녀야 하니, 무엇이 정말 필요한지 정하는 일이 중요하다. 다행히 가져갈 물건은 이미 골라 두었고, 이제 남은 일은 물건을 배낭에 나눠 담는 것뿐이다.

배낭 하나에는 물건을 몇 개든 넣을 수 있지만, 넣은 물건의 무게 합이 그 배낭의 최대 적재량을 넘어서는 안 된다. 물건은 쪼갤 수 없어서 산 배낭의 용량을 다 쓰지 못할 수도 있다.

문제는 배낭이 아직 없어서 사야 한다는 점이다. 가게에는 최대 적재량이 서로 다른 배낭이 여러 개 있고, 값은 모두 같다. 물건을 전부 담을 수 있을 만큼 배낭을 사되, 돈은 가장 적게 쓰는 것이 목표다.

첫째 줄에 담을 물건의 개수 $n$과 가게에 있는 배낭의 개수 $m$이 주어진다. ($1 \le n \le 24$, $1 \le m \le 100$)

둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$이 주어진다. $a_i$는 $i$번째 물건의 무게다. ($1 \le a_i \le 10^8$)

셋째 줄에 $m$개의 정수 $c_1, c_2, \dots, c_m$이 주어진다. $c_i$는 $i$번째 배낭의 최대 적재량이다. ($1 \le c_i \le 10^8$)

첫째 줄에 물건을 모두 담는 데 필요한 배낭의 최소 개수를 출력한다. 물건을 모두 담는 것이 불가능하면 대신 NIE를 출력한다.

첫 번째 예제에서는 첫 번째 배낭과 세 번째 배낭을 사면 된다. 가장 무거운 물건은 적재량이 11인 배낭에 넣고, 남은 물건은 적재량이 9인 배낭에 넣는다.