// Knapsack auction, Roughgarden 4.1-4.2

#include <stdlib.h>
#include <stdio.h>

int n,W;

int v[1001],w[1001],socialWelfare;

char x[1001];

#define GEQpricePerUnit(i,j) (v[i]*w[j]>=v[j]*w[i])   // Is v[i]/w[i] >= v[j]/w[j]?

void readInput() {
  int i;

  scanf("%d %d",&n,&W);

  for (i=1;i<=n;i++)
     scanf("%d",v+i);

  for (i=1;i<=n;i++)
     scanf("%d",w+i);

  // Special case for zero payments.
  v[n+1]=0;
  w[n+1]=1;

  for (i=1;i<=n;i++)
    if (!GEQpricePerUnit(i,i+1)) {
      printf("Bonk at input %d\n",i);
      exit(0);
      }
  }

void allocation() {
  int i,remaining=W;

  socialWelfare=0;
  for (i=1;i<=n;i++)
    if (w[i]<=remaining) {
      remaining-=w[i];
      x[i]=1;
      socialWelfare+=v[i];
      }
    else
      x[i]=0;

  printf("Social welfare:  %d\n",socialWelfare);
  }

void payments() {
  int i,j,lastj,k,remaining;

  printf("Payments determined by lowering price, but bidder is still part of solution\n");
  printf("    i     v     w          p     j     v     w\n");
  for (i=1;i<=n;i++)
    if (x[i]) {
      // Start with v[i+1]/w[i+1] as price
      lastj=i+1;
      for (j=i+2;j<=n+1;j++) {
        // Attempt lowering price to v[j]/w[j]
        remaining=W;
        // Safe to reuse previous successful bids before bid i - can't be rejected
        for (k=1;k<i;k++)
          if (x[k])
            remaining-=w[k];
        // Bid i is moved to "just before" bid j
        for (k=i+1;k<j;k++)
          if (w[k]<=remaining)
            remaining-=w[k];
        // Does bid i get allocated in its new position?
        if (w[i]<=remaining)
          lastj=j;
        else
          break;
        }

      printf("%5d %5d %5d %10.4f %5d %5d %5d\n",i,v[i],w[i],w[i]*((double) v[lastj])/w[lastj],lastj,v[lastj],w[lastj]);
      }
  }

void paymentsDifference() {
  // Roughgarden, Exercise 4.2, p. 50
  int i,j,lastj,k,remaining,socialWelfareNew;

  printf("Payments determined by leaving out bidder and observing increase in social welfare\n");
  printf("    i     v     w     p\n");
  for (i=1;i<=n;i++)
    if (x[i]) {
      socialWelfareNew=0;
      remaining=W;
      for (j=1;j<=n;j++)
        if (j!=i && w[j]<=remaining) {
          remaining-=w[j];
          socialWelfareNew+=v[j];
          }

      printf("%5d %5d %5d %5d\n",i,v[i],w[i],socialWelfareNew-(socialWelfare-v[i]));
      }
  }

int main() {

  readInput();

  allocation();

  payments();

  paymentsDifference();
  }