Riddles
Есенен Турнир по Информатика 2009
Time Limit: 0.2s, Memory Limit: 64MiB
Бабата на Елеонора - Сърча обожава да тормози внуците си с най-различни математически загадки. При последното семейно събиране тя зададе следната такава:

"В един магазин има K стоки с различни цени от 1 до K. Вкъщи имам N монети, подредени в ред A1, A2, ..., AN. Аз искам да отида до магазина и да мога да платя точно всяка една стока. В същото време съм стара жена и не искам да нося твърде много пари в себе си. За това ще взема не всичките N монети, а само първите няколко. Първите колко монети трябва да взема?"

Ели не мисли повече от няколко секунди преди да отговори и да си помисли "Ех, Бабо Сърча, пак ли с тези стандартни алгоритми...". Можете ли и вие да се конкурирате с нея?
Вход
На първия ред от стандартния вход ще са зададени целите числа N и K. На втория ще има N числа Аi – стойностите на монетите в реда, в който Баба Сърча ги има.
Изход
За всеки тест на стандартния изход изведете по едно число – първите колко монети трябва да вземе бабата на Ели, за да може да плати всяка цена от 1 до K. В случай, че това е невъзможно дори ако вземе всичките N, вместо това изведете -1.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ АiK ≤ 1,000,000,000
Примерен Вход Примерен Изход
9 13 5 1 1 2 9 7 11 6 13 5
3 6 3 1 4 -1
4 6 1 4 6 2 4
В първия тест ако вземем първите пет монети (със стойности {5, 1, 1, 2, 9}) можем да образуваме 1 = 1; 1 + 1 = 2; 1 + 2 = 3; 1 + 1 + 2 = 4; 5 = 5; 5 + 1 = 6; 5 + 2 = 7; 5 + 2 + 1 = 8; 9 = 9; 9 + 1 = 10; 9 + 2 = 11; 9 + 1 + 2 = 12; 9 + 1 + 1 + 2 = 13.
Във втория тест е невъзможно да образуваме числото 2 по никакъв начин.
В третия тест въпреки, че монетите 1, 2, и 4 са ни достатъчни, трябва да вземем всичките 4 монети, защото тази със стойност 2 е чак в края на редицата.
Мрън!