Sachverhalt: Sachverhalt: A. O._ war seit Juli 1999 Präsident der Genossenschaft K._, M._ amtete als deren Kassier und Sekretär. Die Genossenschaft führte das Restaurant A._ und war bei der Ausgleichskasse des Kantons Bern als beitragspflichtige Arbeitgeberin angeschlossen. Am 16. Juli 2001 wurde über sie der Konkurs eröffnet und am 12. Oktober 2001 mangels Aktiven wieder eingestellt. Die Ausgleichskasse erliess am 17. Oktober 2002 unter anderem gegen O._ und M._ Schadenersatzverfügungen, mit welchen sie für entgangene AHV/IV/EO/ALV- und FAK-Beiträge inklusive Verzugszinsen den Betrag von je Fr. 42'658.35 verlangte. Die Betroffenen erhoben Einspruch. A. O._ war seit Juli 1999 Präsident der Genossenschaft K._, M._ amtete als deren Kassier und Sekretär. Die Genossenschaft führte das Restaurant A._ und war bei der Ausgleichskasse des Kantons Bern als beitragspflichtige Arbeitgeberin angeschlossen. Am 16. Juli 2001 wurde über sie der Konkurs eröffnet und am 12. Oktober 2001 mangels Aktiven wieder eingestellt. Die Ausgleichskasse erliess am 17. Oktober 2002 unter anderem gegen O._ und M._ Schadenersatzverfügungen, mit welchen sie für entgangene AHV/IV/EO/ALV- und FAK-Beiträge inklusive Verzugszinsen den Betrag von je Fr. 42'658.35 verlangte. Die Betroffenen erhoben Einspruch. B. Die Ausgleichskasse reichte Klagen auf Zahlung von Schadenersatz im verfügten Umfang ein, welche das Verwaltungsgericht des Kantons Bern unter Vereinigung der beiden Verfahren im Umfang von Fr. 21'637.05 guthiess und im weitergehenden Betrag abwies. B. Die Ausgleichskasse reichte Klagen auf Zahlung von Schadenersatz im verfügten Umfang ein, welche das Verwaltungsgericht des Kantons Bern unter Vereinigung der beiden Verfahren im Umfang von Fr. 21'637.05 guthiess und im weitergehenden Betrag abwies. C. O._ und M._ lassen mit dem Antrag Verwaltungsgerichtsbeschwerde führen, der vorinstanzliche Entscheid sei insoweit aufzuheben, als sie zu Schadenersatz verurteilt würden und die Klagen der Ausgleichskasse seien vollumfänglich abzuweisen. Die Ausgleichskasse und das Bundesamt für Sozialversicherung verzichten auf Vernehmlassung.