At first I use DFS but timeout.And then I try to solve it by DP.Finally,I found that normal DFS&optimize cut can be AC in 0.29sec.