Sachverhalt: Sachverhalt: A. Am 8. April 1993 erteilten das Baudepartement und das Finanzdepartement des Kantons St. Gallen der politischen Gemeinde Quarten und der einfachen Gesellschaft "Park Walensee" die bis zum 31. Dezember 2027 befristete Bewilligung, den der Parzelle Nr. 751 in Unterterzen vorgelagerten Teil des Walensees für den Ausbau des bereits bestehenden Bootshafens zu nutzen. Die jährliche Nutzungsentschädigung wurde auf Fr. 8'000.-- festgesetzt. Der Bootshafen wurde von der Bootshafen Unterterzen AG erstellt, an welcher die beiden Bewilligungsnehmer je zur Hälfte beteiligt sind und die den Hafen mit 117 Liegeplätzen auch betreibt. Mit Verfügung vom 11. September 2003 nahm das Tiefbauamt des Kantons St. Gallen eine Anpassung der jährlichen Nutzungsentschädigung vor und setzte diese neu auf Fr. 88'984.-- fest. Gegen diese Erhöhung wandten sich die Politische Gemeinde Quarten, die einfache Gesellschaft Park Walensee und die Bootshafen Unterterzen AG an die Regierung des Kantons St. Gallen, die ihren Rekurs am 11. Mai 2004 abwies. Die von den Rekurrenten gegen diesen Beschluss gerichtete Beschwerde wies das Verwaltungsgericht des Kantons St. Gallen am 9. November 2004 ab. Gegen diese Erhöhung wandten sich die Politische Gemeinde Quarten, die einfache Gesellschaft Park Walensee und die Bootshafen Unterterzen AG an die Regierung des Kantons St. Gallen, die ihren Rekurs am 11. Mai 2004 abwies. Die von den Rekurrenten gegen diesen Beschluss gerichtete Beschwerde wies das Verwaltungsgericht des Kantons St. Gallen am 9. November 2004 ab. B. Mit Verwaltungsgerichtsbeschwerde vom 7. Januar 2005 beantragen die Politische Gemeinde Quarten, die einfache Gesellschaft "Park Walensee" und die Bootshafen Unterterzen AG dem Bundesgericht, das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 9. November 2004 aufzuheben. Das Verwaltungsgericht des Kantons St. Gallen beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Für die Regierung schliesst das Tiefbauamt des Kantons St. Gallen auf Abweisung der Beschwerde.