B'This is the hard version of the problem. The difference between the versions is the constraints on a_i . You can make hacks only if all versions of the problem are solved. Little Dormi has recently received a puzzle from his friend and needs your help to solve it. The puzzle consists of an upright board with n rows and m columns of cells, some empty and some filled with blocks of sand, and m non-negative integers a_1,a_2, ldots,a_m ( 0 <= q a_i <= q n ). In this version of the problem, a_i will always be not greater than the number of blocks of sand in column i . When a cell filled with a block of sand is disturbed, the block of sand will fall from its cell to the sand counter at the bottom of the column (each column has a sand counter). While a block of sand is falling, other blocks of sand that are adjacent at any point to the falling block of sand will also be disturbed and start to fall. Specifically, a block of sand disturbed at a cell (i,j) will pass through all cells below and including the cell (i,j) within the column, disturbing all adjacent cells along the way. Here, the cells adjacent to a cell (i,j) are defined as (i-1,j) , (i,j-1) , (i+1,j) , and (i,j+1) (if they are within the grid). Note that the newly falling blocks can disturb other blocks. In one operation you are able to disturb any piece of sand. The puzzle is solved when there are at least a_i blocks of sand counted in the i -th sand counter for each column from 1 to m . You are now tasked with finding the minimum amount of operations in order to solve the puzzle. Note that Little Dormi will never give you a puzzle that is impossible to solve. The first line consists of two space-separated positive integers n and m ( 1 <= q n cdot m <= q 400 ,000 ). Each of the next n lines contains m characters, describing each row of the board. If a character on a lin'...