3 ms·

If the claim were true that the solution is always integer, then one could use a poly-time LP solver.