Sachverhalt: Mit Verfügungen vom 16. Mai 2002 verpflichtete die Ausgleichskasse des Schweizerischen Baumeisterverbandes G._ und B._, Verwaltungsratsmitglieder der in Konkurs gefallenen Firma M._ AG für nicht mehr erhältliche Sozialversicherungsbeiträge zuzüglich Verzugszinsen, Mahngebühren und Betreibungskosten Schadenersatz im Ausmass vom Fr. 42'040.15 bzw. Fr. 72'521.60 zu leisten, dies in solidarischer Haftbarkeit bis zum kleineren der beiden Beträge. Auf Einspruch der zwei Belangten klagte die Kasse auf Bezahlung der erwähnten Summen. Mit Entscheid vom 23. Mai 2003 hiess das Obergericht des Kantons Schaffhausen die Klagen im Umfang von Fr. 32'587.45 (G._) bzw. Fr. 62'874.35 (B._) gut, dies unter solidarischer Haftung beider bis zum kleineren Betrag. G._ und B._ lassen Verwaltungsgerichtsbeschwerde führen und beantragen, es seien der kantonale Entscheid aufzuheben und die Klagen der Kasse abzuweisen. Die Ausgleichskasse schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde, während das Bundesamt für Sozialversicherung auf eine Vernehmlassung verzichtet.