f=\
lambda n,s:max([next(K:=F(s,n)),next(K,0)])
def F(s,n):
 q,V=[(s,[])],[]
 while q:
  q=sorted(q,key=lambda x:len(x[1]))[::-1];(s,p),*q=q;F=Q=[(s,[],0,0)]
  for S,P,C,I in Q:
   if C-n:
    if I<len(S):Q+=(S[I]+C<=n)*[(S,P+[I],S[I]+C,I+1)]+[(S,P,C,I+1)]
   else:U=sorted(p+[[s[k]for k in P]]);Z=U not in V;q+=Z*[([a for i,a in enumerate(s)if~-(i in P)],U)];V+=Z*[U];F=0
  if F:yield len(p)
 
import re
s = """
1, [1] -> 1
1, [2] -> 0
2, [1] -> 0
1, [1, 1] -> 2
2, [1, 1, 1] -> 1
3, [1, 1, 2, 2] -> 2
9, [1, 1, 3, 3, 5, 5, 7] -> 2
9, [1, 1, 3, 3, 5, 7, 7] -> 1
8, [1, 1, 2, 3, 4, 6, 6, 6] -> 2
6, [1, 1, 2, 2, 3, 3, 3, 5, 6, 8] -> 4
13, [2, 2, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 9, 11, 12] -> 5
22, [1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 13, 14, 14, 17, 18, 18, 21] -> 10
"""
for i in filter(None, s.split('\n')):
	a, b, c = map(eval, re.split(',\s(?=\[)|\s\-\>\s',i))
	assert f(a,b)==c
 
print('tests passed')

Zj1cCmxhbWJkYSBuLHM6bWF4KFtuZXh0KEs6PUYocyxuKSksbmV4dChLLDApXSkKZGVmIEYocyxuKToKIHEsVj1bKHMsW10pXSxbXQogd2hpbGUgcToKICBxPXNvcnRlZChxLGtleT1sYW1iZGEgeDpsZW4oeFsxXSkpWzo6LTFdOyhzLHApLCpxPXE7Rj1RPVsocyxbXSwwLDApXQogIGZvciBTLFAsQyxJIGluIFE6CiAgIGlmIEMtbjoKICAgIGlmIEk8bGVuKFMpOlErPShTW0ldK0M8PW4pKlsoUyxQK1tJXSxTW0ldK0MsSSsxKV0rWyhTLFAsQyxJKzEpXQogICBlbHNlOlU9c29ydGVkKHArW1tzW2tdZm9yIGsgaW4gUF1dKTtaPVUgbm90IGluIFY7cSs9WipbKFthIGZvciBpLGEgaW4gZW51bWVyYXRlKHMpaWZ+LShpIGluIFApXSxVKV07Vis9WipbVV07Rj0wCiAgaWYgRjp5aWVsZCBsZW4ocCkKICAKaW1wb3J0IHJlCnMgPSAiIiIKMSwgWzFdIC0+IDEKMSwgWzJdIC0+IDAKMiwgWzFdIC0+IDAKMSwgWzEsIDFdIC0+IDIKMiwgWzEsIDEsIDFdIC0+IDEKMywgWzEsIDEsIDIsIDJdIC0+IDIKOSwgWzEsIDEsIDMsIDMsIDUsIDUsIDddIC0+IDIKOSwgWzEsIDEsIDMsIDMsIDUsIDcsIDddIC0+IDEKOCwgWzEsIDEsIDIsIDMsIDQsIDYsIDYsIDZdIC0+IDIKNiwgWzEsIDEsIDIsIDIsIDMsIDMsIDMsIDUsIDYsIDhdIC0+IDQKMTMsIFsyLCAyLCAyLCAyLCAzLCAzLCA0LCA1LCA1LCA2LCA4LCA5LCA5LCAxMSwgMTJdIC0+IDUKMjIsIFsxLCAxLCAyLCAzLCAzLCAzLCAzLCAzLCA0LCA0LCA0LCA1LCA2LCA2LCA3LCA3LCA3LCA4LCA5LCA5LCAxMCwgMTMsIDE0LCAxNCwgMTcsIDE4LCAxOCwgMjFdIC0+IDEwCiIiIgpmb3IgaSBpbiBmaWx0ZXIoTm9uZSwgcy5zcGxpdCgnXG4nKSk6CglhLCBiLCBjID0gbWFwKGV2YWwsIHJlLnNwbGl0KCcsXHMoPz1cWyl8XHNcLVw+XHMnLGkpKQoJYXNzZXJ0IGYoYSxiKT09YwoKcHJpbnQoJ3Rlc3RzIHBhc3NlZCcp