Problem:


Problem B: For the Peace

This is a story of a world somewhere far from the earth. In this world, the land is parted into a
number of countries ruled by empires. This world is not very peaceful: they have been involved
in army race.

They are competing in production of missiles in particular. Nevertheless, no countries have
started wars for years. Actually they have a reason they can’t get into wars - they have
missiles much more than enough to destroy the entire world. Once a war would begin among
countries, none of them could remain.

These missiles have given nothing but scare to people. The competition has caused big financial
and psychological pressure to countries. People have been tired. Military have been tired. Even
empires have been tired. No one wishes to keep on missile production.

So empires and diplomats of all countries held meetings quite a few times toward renouncement
of missiles and abandon of further production. The meetings were quite difficult as they have
different matters. However, they overcame such difficulties and finally came to the agreement
of a treaty. The points include:

    
 Each country will dispose all the missiles of their possession by a certain date.

    
 The war potential should not be different by greater than a certain amount d among all
      countries.

Let us describe more details on the second point. Each missile has its capability, which represents
how much it can destroy the target. The war potential of each country is measured simply by
the sum of capability over missiles possessed by that country. The treaty requires the difference
to be not greater than d between the maximum and minimum potential of all the countries.

Unfortunately, it is not clear whether this treaty is feasible. Every country is going to dispose
their missiles only in the order of time they were produced, from the oldest to the newest. Some
missiles have huge capability, and disposal of them may cause unbalance in potential.

Your task is to write a program to see this feasibility.

Input

The input is a sequence of datasets. Each dataset is given in the following format:

n d

m1 c1,1 ... c1,m1

...

mn cn,1 ... cn,mn

The first line contains two positive integers n and d, the number of countries and the tolerated
difference of potential (n ≤ 100, d ≤ 1000). Then n lines follow. The i-th line begins with a
non-negative integer mi, the number of the missiles possessed by the i-th country. It is followed
by a sequence of mi positive integers. The j-th integer ci,j represents the capability of the j-th
newest missile of the i-th country (ci,j ≤ 1000). These integers are separated by a single space.
Note that the country disposes their missiles in the reverse order of the given sequence.

The number of missiles is not greater than 10000. Also, you may assume the difference between
the maximum and minimum potential does not exceed d in any dataset.

The input is terminated by a line with two zeros. This line should not be processed.

Output

For each dataset, print a single line. If they can dispose all their missiles according to the treaty,
print "Yes" (without quotes). Otherwise, print "No".

Note that the judge is performed in a case-sensitive manner. No extra space or character is
allowed.

Sample Input

3 3
3 4 1 1
2 1 5
2 3 3
3 3
3 2 3 1
2 1 5
2 3 3
0 0

Output for the Sample Input

Yes
No



Sample input:
3 3
3 4 1 1
2 1 5
2 3 3
3 3
3 2 3 1
2 1 5
2 3 3
0 0


Sample output:
Yes
No

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,d = LI()
        if n == 0:
            break

        a = [LI()[1:] for _ in range(n)]
        q = []
        sa = []
        for ai in a:
            s = sum(ai)
            sa.append([s, ai])

        f = True
        while f:
            f = False
            sa.sort()
            ls,la = sa[-1]
            if ls == 0:
                break
            ls2 = sa[-2][0]
            if ls - la[0] >= ls2 - d:
                sa[-1] = [ls-la[0], la[1:]]
                sa.sort()
                f = True
                continue
            for i in range(n-2,-1,-1):
                ts, ta = sa[i]
                if ts == 0:
                    break
                if ts - ta[0] >= ls - d:
                    sa[i] = [ts - ta[0], ta[1:]]
                    f = True

        if sa[-1][0] == 0:
            rr.append('Yes')
        else:
            rr.append('No')

    return '\n'.join(map(str,rr))



print(main())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,d = LI()
        if n == 0:
            break

        a = [LI()[1:] for _ in range(n)]
        q = []
        sa = []
        for ai in a:
            s = sum(ai)
            sa.append([s, ai])

        f = True
        while f:
            f = False
            sa.sort()
            ls,la = sa[-1]
            if ls == 0:
                break
            ls2 = sa[-2][0]
            if ls - la[-1] >= ls2 - d:
                sa[-1] = [ls - la[-1], la[:-1]]
                f = True
                continue

            for i in range(n-2,-1,-1):
                ts, ta = sa[i]
                if ts == 0:
                    break
                if ts - ta[-1] >= ls - d:
                    sa[i] = [ts - ta[-1], ta[:-1]]
                    f = True

        if sa[-1][0] == 0:
            rr.append('Yes')
        else:
            rr.append('No')

    return '\n'.join(map(str,rr))



print(main())