Tri de problèmes – Épreuve régionale 2009

En demi-finale, chaque problème est affecté à un niveau (un entier) et vous devez les résoudre dans l'ordre.

Pour déterminer ces niveaux, l'équipe de Prologin rassemble tous les problèmes écrits, et leur donne à chacun une note de difficulté suivant plusieurs critères (au nombre de M) : longueur de code nécessaire, structures de données à utiliser, réflexion à mener par exemple.

Un problème A est alors plus facile qu'un problème B si et seulement si l'on peut réarranger les notes attribuées au problème A pour qu'à chacune corresponde une note de B plus élevée (au sens large). Ainsi, un problème recevant les notes 2 et 8 est plus facile qu'un problème recevant les notes 10 et 5 car on peut réarranger (2,8) en (8,2) afin d'avoir (8,2) \<= (10, 5) (car 8 \<= 10 et 2 \<= 5).

Un problème A est par ailleurs strictement plus facile qu'un problème B si et seulement s'il est plus facile que ce problème et qu'au moins une des notes est strictement inférieure à la note qui lui correspond dans le réarrangement considéré.

Un problème A qui n'a aucun problème strictement plus facile que lui est alors de niveau 1. Sinon et si tous les problèmes strictement plus faciles que lui sont de niveau 1, il sera de niveau 2. Sinon et si tous les problèmes strictement plus faciles que lui sont de niveau 1 ou 2, il sera de niveau 3, et ainsi de suite.

Attention : si l'on veut comparer deux problèmes A et B et qu'avec notre définition on n'a ni A strictement plus facile que B, ni B strictement plus facile que A, cela signifie que l'équipe de Prologin est incapable de comparer les difficultés des problèmes A et B. Cela ne signifie pas que A et B sont de même niveau.

Quel est le niveau maximum représenté dans les problèmes proposés ?

ENTREE

N nombre de problèmes, M nombre de caractéristiques, suivis de N lignes de M entiers.

LIMITES

N \<= 2000, M \<= 100

SORTIE

Sur une seule ligne, le niveau maximum présent dans l'entrée.