Le croissant saboteur P87011

Enguany, n equips van participar al SWERC, amb un total d’m problemes per resoldre. Aquesta competició la guanya l’equip que resol estrictament més problemes que la resta. (Realment hi ha un sistema de desempat, però en aquest problema l’ignorem.) Tanmateix, en Lucien, el black croissant hacker més famós de París, també era l’entrenador d’un dels equips que van participar, i va sabotejar la competició per intentar guanyar.

En Lucien, que sabia quins problemes resoldria cada equip, va aconseguir infiltrar-se al jutge per sabotejar alguns problemes, que així no podrien ser resolts per cap equip. Tanmateix, per evitar alarmar els organitzadors del SWERC, en Lucien va decidir no sabotejar més de k ‍problemes. Amb aquesta informació, podeu determinar si en Lucien va poder fer que el seu equip guanyés?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, m i k, seguits d’n files amb m caràcters cadascuna. El j-èsim caràcter de la i-èsima fila és 1 si l’equip i és capaç de resoldre el problema j, i 0 altrament. L’equip d’en Lucien sempre és el de la primera fila. Poseu suposar 2 ≤ n ≤ 25, 2 ≤ m ≤ 25, i 0 ≤ k ≤ m.

Sortida

Per a cada cas, escriviu “OUI” si l’equip d’en Lucien va poder guanyar el SWERC, i “NON” altrament.

Pista

La solució esperada d’aquest problema és un backtracking bastant optimitzat.