Faits: Faits: A. Les alinéas 2 et 3 de l'art. 4ter de la loi valaisanne du 12 novembre 1982 concernant le traitement du personnel enseignant des écoles primaires, du cycle d'orientation et des écoles secondaires du deuxième degré (ci-après: LTPE), introduits par la modification législative du 20 juin 1995, ont la teneur suivante: "2 Par voie d'ordonnance, le Conseil d'Etat peut instituer, lors de l'engagement, des paliers d'attente entraînant une réduction du traitement fixé par les dispositions légales ordinaires de: - 6 % la première année - 4 % la deuxième année - 2 % la troisième année 3 Si le marché du travail le demande, et la situation financière et économique du canton le permet, le Conseil d'Etat peut, par voie d'ordonnance, augmenter de manière adéquate le traitement fixé par le plan de classement, jusqu'à un maximum de 5 %." L'art. 15 al. 1 de l'ordonnance d'exécution du 30 septembre 1983 de la loi précitée (ci-après: OTPE), modifié le 13 décembre 1995, prévoit que "lors de l'engagement, le traitement fixé par les dispositions légales ordinaires est réduit selon les paliers suivants: - premier palier: 6 % - deuxième palier: 4 % - troisième palier: 2 %." Ce système, dit des paliers d'attente, a été introduit pour des raisons financières; il est entré en vigueur le 1er janvier 1996 dans l'administration cantonale et à partir de l'année scolaire 1996/1997 dans l'enseignement. Le 20 décembre 2002, le Département cantonal de l'éducation, de la culture et du sport (ci-après: le Département cantonal) a informé les enseignants que le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) avait décidé de supprimer deux paliers d'attente, celui de 94 % à partir du 1er septembre 2002 et celui de 96 % à partir du 1er septembre 2003. Le 20 décembre 2002, le Département cantonal de l'éducation, de la culture et du sport (ci-après: le Département cantonal) a informé les enseignants que le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) avait décidé de supprimer deux paliers d'attente, celui de 94 % à partir du 1er septembre 2002 et celui de 96 % à partir du 1er septembre 2003. B. X._ a été engagé le 1er septembre 1999 en qualité d'enseignant au cycle d'orientation de Y._. Pour sa première année d'engagement, il a reçu 94 % du traitement fixé par les dispositions légales ordinaires. Pour l'année scolaire 2000/2001, il a obtenu 96 % du traitement; pour l'année scolaire 2001/2002, 98 % et, dès l'année scolaire 2002/2003, 100 %. Le 3 mars 2003, X._ a demandé à la Section des traitements de l'Administration cantonale des finances un réajustement de son salaire de 5 % équivalant à la suppression de deux paliers d'attente. Il estimait que ce "rattrapage" correspondait au sacrifice financier qu'il avait dû consentir, dès lors que les paliers d'attente avaient créé artificiellement une diminution salariale non justifiée entre des enseignants de même fonction exerçant une activité semblable, en fonction de la date de leur engagement. Par décision du 11 mars 2003, le Département cantonal a rejeté cette requête au motif que le Service de l'enseignement n'avait fait qu'appliquer à l'égard de l'intéressé les dispositions légales en vigueur et valables pour tous les enseignants se trouvant dans la même situation que la sienne. Le 9 septembre 2003, le Conseil d'Etat a rejeté le recours dirigé contre la décision précitée. Il a retenu en bref que la suppression des paliers d'attente sans compensations ne constituait pas une violation de l'art. 8 Cst. et que l'acceptation de la requête de X._ entraînerait une atteinte au respect du budget. Le 9 septembre 2003, le Conseil d'Etat a rejeté le recours dirigé contre la décision précitée. Il a retenu en bref que la suppression des paliers d'attente sans compensations ne constituait pas une violation de l'art. 8 Cst. et que l'acceptation de la requête de X._ entraînerait une atteinte au respect du budget. C. A l'encontre de cette décision, X._ a formé, d'une part, le 30 septembre 2003, un recours de droit administratif auprès du Tribunal cantonal du canton du Valais, Cour de droit public (ci-après: le Tribunal cantonal) et, d'autre part, le 8 octobre 2003, un recours de droit public auprès du Tribunal fédéral. Par ordonnance présidentielle du 17 novembre 2003, la procédure fédérale a été suspendue jusqu'à droit connu au plan cantonal. Le 20 février 2004, le Tribunal cantonal a rejeté le recours dont il était saisi. Il a jugé en substance que la pénalisation au plan de la rétribution dont se plaignait X._ résultait de la volonté du législateur et qu'elle ne violait pas le principe de l'égalité de traitement dans la mesure où la situation de l'intéressé et celle des enseignants engagés postérieurement à la suppression des paliers d'attente ne reposaient pas sur les mêmes conditions objectives. D. Agissant le 8 mars 2004 par la voie du recours de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 20 février 2004 et de lui renvoyer le dossier pour nouvelle décision dans le sens des considérants. Il se plaint que la décision entreprise soit arbitraire et viole l'art. 8 Cst., qui consacre le principe de l'égalité. Son argumentation tend à démontrer qu'il devrait recevoir une rémunération supérieure, correspondant à celle d'un professeur engagé postérieurement à lui-même et pouvant bénéficier dès son engagement de la suppression des paliers d'attente. Le Tribunal cantonal et le Conseil d'Etat renoncent à formuler des observations. Le Tribunal cantonal et le Conseil d'Etat renoncent à formuler des observations. E. Par décision du 8 avril 2004, le Tribunal fédéral a prononcé que le recours déposé le 8 octobre 2003 était devenu sans objet et a rayé la cause du rôle. 