The Mediterranean coast of North Africa had long been a hotbed of piracy. Most nations, including the United States, dealt with the threat by paying "tribute" (bribes) to the rulers of the Barbary States (Morocco, Algiers, Tripoli and Tunisia). The Americans had paid $2 million in tribute in its first 10 years of existence. A crisis developed in 1801 when the dey of Algiers demanded more tribute than usual. The United States employed a naval blockade and diplomacy as a means to end the pirate threats, but to no avail. In 1804, naval Lieutenant Stephen Decatur led a raid in the harbor at Tripoli, which was highlighted by the destruction of the Philadelphia, a captured U.S. ship in Tripolitan hands. Hostilities with Tripoli were concluded by treaty in 1805, but problems with the other Barbary States remained until the end of the War of 1812. The exploits of the American forces in the Tripolitan War were widely reported in the newspapers and brought increased prestige to the emerging navy. Jefferson set aside his party's pacifism and pursued a more militant course, believing that this was in the nation's best interest. This conflict was later memorialized in the opening words of the Marine Hymn, "From the halls of Montezuma to the shores of Tripoli."