Sachverhalt: Sachverhalt: A. Die Schweizerischen Bundesbahnen SBB (heute: SBB AG; Beschwerdegegnerin) schrieben am 21. Januar 1994 im Rahmen eines Submissionsverfahrens u.a. die Arbeiten für den Tunnel St-Aubin-Sauges aus. Im Hinblick auf den Abschluss des entsprechenden Werkvertrages bildeten fünf Gesellschaften bzw. Unternehmer am 18. Oktober 1994 ein Konsortium in der Rechtsform einer einfachen Gesellschaft (Groupement Tunnel de St-Aubin, GTS, heute bestehend aus: A._ Tunnelbau AG, A._ SA, B._ SA, Konkursmasse C._ sowie Konkursmasse D._ SA in Liquidation, [Beschwerdeführerinnen]). Die Beschwerdeführerinnen reichten eine Offerte für insgesamt Fr. 59'452'051.-- ein. Mit Schreiben vom 29. November 1994 teilte ihnen die Beschwerdegegnerin mit, dass sie den Zuschlag sowohl für das Los 1 (Fels) als auch für das Los 2 (lockere Erde) des Tunnels erhalten hätten. Am 20. Februar/ 30. März 1995 unterzeichneten die Parteien einen Werkvertrag, in dem ein Werklohn von Fr. 55'888'911.10 (Fr. 54'918'070.85 + MWST) vorgesehen wurde. Die Arbeiten wurden am 10. Januar 1995 aufgenommen und endigten am 30. Juni 1998. Am 13. Oktober 1999 reichten die Beschwerdeführerinnen eine Schlussrechnung "hors revendications" (unter Vorbehalt von Nachforderungen) ein. Die Beschwerdegegnerin zahlte insgesamt einen Betrag von Fr. 51'425'890.--. Die Beschwerdeführerinnen erhoben nachträglich verschiedene Mehrforderungen: A.a Die Aushubarbeiten für den Tunnel St-Aubin-Sauges waren teilweise mit Sprengstoff vorgenommen worden. Die Beschwerdeführerinnen machten insoweit geltend, die Geschwindigkeit, mit der solche Arbeiten vorangetrieben werden könnten, hänge unter anderem von der Beschaffenheit des Gesteins ab, die durch den so genannten K-Faktor (oder K-Wert) beschrieben werde. Der K-Faktor des Gesteins sei ungünstiger gewesen als in den Offertunterlagen angenommen. Zur Einhaltung der geforderten Erschütterungsgrenzwerte hätten deshalb die Aushublängen verringert, mithin eine Änderung des Sprengplanes vorgenommen werden müssen. Daraus hätten Mehrkosten von Fr. 611'278.-- resultiert, die zu Lasten der Beschwerdegegnerin gingen, da sie das Risiko einer Abweichung vom angenommenen K-Wert zu tragen habe. A.b Um die vertraglichen Fristen trotz der auf die Abweichung des K-Werts zurückzuführenden Verzögerung einhalten zu können, sei es erforderlich gewesen, den Betonierrhythmus zu erhöhen. Dazu sei ein zweites Schalungsset verwendet worden, für das die Beschwerdeführerinnen der Beschwerdegegnerin Mehrkosten von Fr. 60'000.-- in Rechnung stellten. A.c Zur Erhöhung des Betonierrhythmus habe sodann Beton bei einem anderen Lieferanten zugekauft werden müssen. Dies habe auch dazu gedient, zusätzliche witterungsbedingte Verzögerungen wettzumachen. Der Bezug von Beton bei Dritten habe Mehrkosten von Fr. 1'009'742.-- verursacht, für die ebenfalls die Beschwerdegegnerin das Risiko trage. A.d Die auf die Abweichung des K-Werts und auf ungünstige Witterung zurückzuführende Verzögerung der Aushubarbeiten habe zu einer grossen Verlängerung der Dauer geführt, während der Produktionsmittel der Beschwerdeführerinnen hätten eingesetzt werden müssen. Dafür seien sie mit Fr. 6'528'162.-- zu entschädigen. A.e Die Parteien hatten vereinbart, dass der im Tunnel verbaute Beton nach Einheitspreis und grundsätzlich für die effektiv verwendete Menge abgerechnet werden soll. Davon ist unbestrittenermassen ein Abzug für die Betonmenge vorzunehmen, die benötigt wird, um ein beim Aushub entstandenes Überprofil auszugleichen, das resultiert, wenn bei den Aushubarbeiten mehr Gestein entfernt wird, als für die Realisierung des Tunnels eigentlich nötig wäre (Strafzahlung für sog. Überprofilbeton). Die Beschwerdeführerinnen machten insoweit geltend, bei richtiger Berechnung des Überprofilbeton-Volumens sei bloss eine Preisreduktion von Fr. 61'047.65 berechtigt. In der Schlussabrechnung habe sie Fr. 686'125.-- zu viel abgezogen. A.f Die Bauleitung habe die Beschwerdeführerinnen sodann während der Ausbrucharbeiten angewiesen, das Aushubprofil von 5.60 m auf 5.55 m zu reduzieren. Nach Beendigung der Ausbrucharbeiten habe sich ergeben, dass eine Neuprofilierung des Tunnels erforderlich sei, um den Innenradius einhalten zu können. Dies habe Mehrkosten von Fr. 212'761.-- zur Folge gehabt, für welche die Beschwerdegegnerin einzustehen habe. A.g Schliesslich machten die Beschwerdeführerinnen geltend, die Beschwerdegegnerin habe nach Vertragsschluss zahlreiche Positionen aus dem Leistungsverzeichnis gestrichen, obwohl dieses unveränderlicher Natur sei. Dies habe ihre auf dem Leistungsverzeichnis basierende Preiskalkulation derart erschüttert, dass eine zusätzliche Entschädigung für nicht gedeckte Fix- und allgemeine Geschäftsunkosten sowie für Risiko und Gewinn in der Höhe von Fr. 5 Mio. geboten sei. A.g Schliesslich machten die Beschwerdeführerinnen geltend, die Beschwerdegegnerin habe nach Vertragsschluss zahlreiche Positionen aus dem Leistungsverzeichnis gestrichen, obwohl dieses unveränderlicher Natur sei. Dies habe ihre auf dem Leistungsverzeichnis basierende Preiskalkulation derart erschüttert, dass eine zusätzliche Entschädigung für nicht gedeckte Fix- und allgemeine Geschäftsunkosten sowie für Risiko und Gewinn in der Höhe von Fr. 5 Mio. geboten sei. B. Mit Klage vom 20. Februar 2002 beantragten die Beschwerdeführerinnen dem Handelsgericht des Kantons Bern, die Beschwerdegegnerin zu verpflichten, ihnen Fr. 14'505'762.-- (Fr. 14'108'068.-- + MWST) nebst Zins zu 7,06 % seit dem 30. September 1996 zu bezahlen. Das Handelsgericht hiess die Klage mit Urteil vom 22./23. Januar 2004 lediglich im Zusammenhang mit der Neuprofilierung des Tunnels im Umfang von Fr. 40'000.-- nebst Zins gut und wies sie im Mehrumfang ab. B. Mit Klage vom 20. Februar 2002 beantragten die Beschwerdeführerinnen dem Handelsgericht des Kantons Bern, die Beschwerdegegnerin zu verpflichten, ihnen Fr. 14'505'762.-- (Fr. 14'108'068.-- + MWST) nebst Zins zu 7,06 % seit dem 30. September 1996 zu bezahlen. Das Handelsgericht hiess die Klage mit Urteil vom 22./23. Januar 2004 lediglich im Zusammenhang mit der Neuprofilierung des Tunnels im Umfang von Fr. 40'000.-- nebst Zins gut und wies sie im Mehrumfang ab. C. Die Beschwerdeführerinnen gelangten gegen dieses Urteil mit kantonalrechtlicher Nichtigkeitsklage wegen Verletzung des Anspruchs auf rechtliches Gehör an das Plenum des Appellationshofs des Kantons Bern. Dieses wies das Rechtsmittel am 25. August 2004 ab, soweit es darauf eintrat. Eine dagegen gerichtete staatsrechtliche Beschwerde der Beschwerdeführerinnen hat das Bundesgericht mit Urteil vom heutigen Tag abgewiesen, soweit es darauf eingetreten ist (Verfahren 4P.234/2004). C. Die Beschwerdeführerinnen gelangten gegen dieses Urteil mit kantonalrechtlicher Nichtigkeitsklage wegen Verletzung des Anspruchs auf rechtliches Gehör an das Plenum des Appellationshofs des Kantons Bern. Dieses wies das Rechtsmittel am 25. August 2004 ab, soweit es darauf eintrat. Eine dagegen gerichtete staatsrechtliche Beschwerde der Beschwerdeführerinnen hat das Bundesgericht mit Urteil vom heutigen Tag abgewiesen, soweit es darauf eingetreten ist (Verfahren 4P.234/2004). D. Die Beschwerdeführerinnen beantragen dem Bundesgericht zudem mit staatsrechtlicher Beschwerde vom 16. Juni 2004, das Urteil des Handelsgerichts vom 22./23. Januar 2004 aufzuheben und die Sache zu neuer Entscheidung im Sinne der Erwägungen an das Handelsgericht zurückzuweisen. Sie rügen, dieses habe bei seinen Sachverhaltsfeststellungen und bei der Anwendung von kantonalem Zivilprozessrecht gegen das Willkürverbot verstossen. Die Beschwerdegegnerin beantragt mit Eingabe vom 26. November 2004, die staatsrechtliche Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Handelsgericht hat sich mit Vernehmlassung vom 22. Oktober 2004 zur Beschwerde geäussert, ohne einen bestimmten Antrag zu stellen. Die Beschwerdegegnerin beantragt mit Eingabe vom 26. November 2004, die staatsrechtliche Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Handelsgericht hat sich mit Vernehmlassung vom 22. Oktober 2004 zur Beschwerde geäussert, ohne einen bestimmten Antrag zu stellen. E. Parallel zur vorliegenden Beschwerde haben die Beschwerdeführerinnen in gleicher Sache eidgenössische Berufung erhoben (Verfahren 4C.256/2004).