The answer is $12$, achieved by the following: [asy][asy] for(int i = 0; i < 5; ++i) { draw((0, i)--(4, i)); draw((i, 0)--(i, 4)); } draw((0.5, 3.5)--(2.5,3.5)); draw((3.5, 3.5)--(3.5,1.5)); draw((3.5,0.5)--(1.5,0.5)); draw((0.5,0.5)--(0.5,2.5)); draw((1.5,3.5)--(1.5,2.5)); draw((2.5,2.5)--(3.5,2.5)); draw((2.5,1.5)--(2.5,0.5)); draw((0.5,1.5)--(1.5,1.5)); [/asy][/asy] Call a cell singly-covered if it's covered by exactly one block. By the third condition each block contains at least one singly-covered cell, which instantly implies $k \leq a$. Moreover, we can see easily that each cell is covered by at most three blocks, because if a cell were covered by four, all of its neighbors would be singly-covered, making it impossible to cover one of the corners. Therefore there are at most $3(16 - a) = 48 - 3a$ blocks that cover exactly one singly-covered cell, leading to having at least $a - (48 - 3a) = 4a - 48$ singly-covered cells outside of these blocks, and at most $48 - 3a + \frac{4a - 48}{2} = 24 - a$ blocks in all. By averaging the estimates $k \leq a$ and $k \leq 24 - a$ we get $k \leq 12$ as desired.