As is known, the airline "Trouble" often loses luggage, and concerned journalists decided to calculate the maximum number of luggage pieces that may not return to travelers. The airline "Trouble" operates flights between (n) airports, numbered from (1) to (n). The journalists' experiment will last for (m) days. It is known that at midnight before the first day of the experiment, there were (s_j) lost pieces of luggage in the (j)-th airport. On the (i)-th day, the following occurs: In the morning , (2n) flights take off simultaneously, including (n) flights of the first type and (n) flights of the second type . The (j)-th flight of the first type flies from airport (j) to airport ((((j-2) \bmod n )+ 1)) (the previous airport, with the first airport being the last), and it can carry no more than (a_{i,j}) lost pieces of luggage. The (j)-th flight of the second type flies from airport (j) to airport (((j \bmod n) + 1)) (the next airport, with the last airport being the first), and it can carry no more than (c_{i,j}) lost pieces of luggage. The (j)-th flight of the first type flies from airport (j) to airport ((((j-2) \bmod n )+ 1)) (the previous airport, with the first airport being the last), and it can carry no more than (a_{i,j}) lost pieces of luggage. The (j)-th flight of the second type flies from airport (j) to airport (((j \bmod n) + 1)) (the next airport, with the last airport being the first), and it can carry no more than (c_{i,j}) lost pieces of luggage. In the afternoon , a check of lost luggage is conducted at the airports. If after the flights have departed on that day, there are (x) pieces of luggage remaining in the (j)-th airport and (x \ge b_{i, j}), then at least (x - b_{i, j}) pieces of luggage are found, and they cease to be lost . In the evening , all (2n) flights conclude, and the lost luggage transported that day