2806. 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.