#Mathematica, 147 bytes
t={};s={1};(For[i=1,i<10^3,i++,While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1}];First@SortBy[t,Total])&
ZaMoC
- 24.9k
- 2
- 30
- 81