Acte de grâce – Regional event 2011

Level 3

Énoncé

Joseph Marchand a décroché son job rêvé : gardien de prison. Aujourd'hui, il doit libérer certains prisonniers (la famille avant tout), mais ces fichus interrupteurs qu'il doit manipuler ouvrent plusieurs grilles à la fois. Par souci d'économie d'énergie, Joseph veut en actionner le moins possible. Bien entendu, il ne faut surtout pas garder sous cellule des prisonniers graciés, ni laisser sortir des prisonniers non libérés.

Entrée

  • Sur la première ligne, le nombre P de prisonniers.
  • Sur la deuxième ligne, l'acte de grâce représentant les prisonniers à libérer (le k-ième entier indique si le prisonnier n° k est gracié (1) ou non (0)).
  • Sur la troisième ligne, le nombre N d'interrupteurs.
  • Sur les N lignes suivantes, un interrupteur par ligne (le k-ième entier indique si l'interrupteur ouvre la cellule n° k (1) ou non (0)).

Sortie

  • Le nombre minimal d'interrupteurs à actionner afin de libérer tous les prisonniers graciés.

Contraintes

  • 1 <= P <= 30
  • 1 <= N <= 300

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
3000 milliseconds

Input/output samples

Sample input
3
1 1 1
5
0 0 1
1 0 0
0 1 0
0 0 0
0 0 0
Sample output
3
Sample input
4
1 1 1 1
7
1 0 1 1
0 1 1 0
1 0 1 1
1 1 1 0
0 1 0 1
1 1 0 1
0 1 0 1
Sample output
2

Submit your solution

You have to register or log in to be able to submit your solution.