My algo is O(p*n*logn).

Algo:
1)sort pairs <d,s> by d.  We get d1<=d2<=d3<=...<=dn.
                                 s1  s2  s3       sn
2)For each p we choose a minimal k (if exist pairs <ki,p> and <kj,p> where ki<kj then we delete <kj,p>

3)ans=s[1]+...+s[n]-(x1+x2+...+xn)/100 where xi=s[i]*di or xi=s[i]*p if we choose p (if we choose p => the minimum of the k elements of x are equal to s*p), i=1..n

=> we must max_sum=(x1+x2+...+xn)->max
=>ans=s[1]+...+s[n]-max_sum/100

4)max_sum=s1*d1+...+sn*dn
For each p=1..100 find 1<=j<=n | p<dj, j->min (if there is no such j => max_sum=max(max_sum, (s[1]+...+s[n])*p) )
  then we take (s[1]+...+s[j-1])*p (s[0]=0); if we took <k elements then we must take lost=k-(j-1) elements from sj,...,sn. We must choose such index i1<i2<...<ilost from j..n | s[i1]*(d[i1]-p)=min(s[i]*(d[i]-p), j<=i<=n, s[i2]*(d[i2]-p)=min(s[i]*(d[i]-p), j<=i<=n,i!=i1, ... .
  then max_sum=max(max_sum, (s[1]+...+s[j-1])*p + (s[i1]+...+s[ilost])*p+Sum(si*di, j<=i<=n and i<>ik,k=1..lost)).

Edited by author 28.06.2017 15:34