Simple recursion from highest weight down to lowest with proper cut-off on maximal reachable weight and caching of results gives AC in 0.015 sec and 1Mb RAM. I write that spoiler here because I suspects that tests are very weak because I have no proof of why this straightforward thing works so fast when problem has 4-sec/256Mb limits.