By April 9, Polish troops reached Royal Prussia, capturing Bydgoszcz and Nakło (April 19). Polish attempt to capture Toruń, on April 17, was a failure. After a short rest, Stefan Czarniecki considered a raid of Swedish Pomerania, but other Polish leaders opposed this idea. Charles Gustav decided to prevent the Poles from taking control of the northern districts of the country, and departed Warsaw with an army of 10,000 (April 17). On April 21, the Lithuanians under Sapieha freed Lublin, and on April 23, the Lithuanian army reached Praga, which today is a right-bank district of Warsaw. The forces of Czarniecki and Lubomirski joined other troops near Piła, but on May 7 they were defeated in the Battle of Kłecko, despite their numerical superiority. After the battle, the surviving Polish units regrouped near Gniezno, and in late May, they headed for Warsaw, to help the Lithuanians in the siege of the Polish capital (April 24 - July 1). Warsaw was being defended by Arvid Wittenberg with 2,000 soldiers, as the main Swedish army was busy besieging Gdańsk. Wittenberg capitulated on July 1, 1656. Already in late 1655, Charles Gustav realized that it would be impossible for him to control the Commonwealth. The Swedish king decided to find allies, who would help him to divide Poland-Lithuania. On June 29, 1656, he signed the Treaty of Marienburg, in which he offered Frederick William, Elector of Brandenburg a reward for fighting on his side. Brandenburg-Prussia was promised sovereignty in four voivodeships - Poznań, Kalisz, Łęczyca, and Sieradz. On July 28, a re-enforced Swedish–Brandenburgian army, under Charles Gustav, set out for Warsaw. Even though the allied army was smaller, it still managed to defeat the Poles and Lithuanians in the Battle of Warsaw (1656) (July 28–30), and to recapture Warsaw. This victory, hovewer, achieved little, as the Poles retreated behind the Wieprz, where they regrouped, and were soon ready to continue fighting. Finally, Charles Gustav decided to abandon Warsaw, and retreat to Royal Prussia. To punish Brandenburg-Prussia, Commonwealth forces decided to invade the Duchy of Prussia.