小 G 有一个长度为 的 的网格条带，格子从左到右编号为 。有 种颜料，第 种颜料对应颜色编号 。不同编号的颜料视为不同颜色，即使它们的费用或可用区间相同，也仍然是不同颜色。
第 种颜料只能用于编号在区间 内的格子。若某个格子使用第 种颜料，则需要花费 的代价。每种颜料可以被使用任意多次。
现在，小 G 想在每一个格子内都涂上一种可用的颜料。也就是说，对于每个格子 ，若选择第 种颜料，则必须满足 。
小 G 希望这个网格条带内颜色尽量丰富，所以任意连续 个格子内的颜色不能全部相同。小 G 想知道，涂色的总代价最小是多少？如果不存在满足条件的染色方式，输出 .
