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 des Unternehmens 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 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. Eine von den Beschwerdeführerinnen gegen diesen Entscheid erhobene kantonalrechtliche Nichtigkeitsklage wegen Verletzung des Anspruchs auf rechtliches Gehör wies das Plenum des Appellationshofs des Kantons Bern (im Folgenden: der Appellationshof) mit Urteil vom 25. August 2004 ab, soweit es darauf eintrat. Eine von den Beschwerdeführerinnen gegen diesen Entscheid erhobene kantonalrechtliche Nichtigkeitsklage wegen Verletzung des Anspruchs auf rechtliches Gehör wies das Plenum des Appellationshofs des Kantons Bern (im Folgenden: der Appellationshof) mit Urteil vom 25. August 2004 ab, soweit es darauf eintrat. C. Die Beschwerdeführerinnen beantragen dem Bundesgericht mit staatsrechtlicher Beschwerde vom 7. Oktober 2004, dieses Urteil aufzuheben und die Sache zu neuer Entscheidung im Sinne der Erwägungen an den Appellationshof zurückzuweisen. Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Der Appellationshof hat auf eine Vernehmlassung verzichtet. Die Beschwerdegegnerin beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Der Appellationshof hat auf eine Vernehmlassung verzichtet. D. Die Beschwerdeführerinnen haben das Urteil des Handelsgerichts vom 22./23. Januar 2004 ausser mit der kantonalen Nichtigkeitsklage auch mit staatsrechtlicher Beschwerde (Verfahren 4P.152/2004) sowie mit eidgenössischer Berufung (Verfahren 4C.256/2004) angefochten. D. Die Beschwerdeführerinnen haben das Urteil des Handelsgerichts vom 22./23. Januar 2004 ausser mit der kantonalen Nichtigkeitsklage auch mit staatsrechtlicher Beschwerde (Verfahren 4P.152/2004) sowie mit eidgenössischer Berufung (Verfahren 4C.256/2004) angefochten. E. Ein Gesuch der Beschwerdeführerinnen, es sei der Beschwerde vom 7. Oktober 2004 hinsichtlich der Parteikosten die aufschiebende Wirkung zu gewähren, hat der Präsident der I. Zivilabteilung des Bundesgerichts mit Verfügung vom 11. Oktober 2004 abgewiesen.