Laundry

Memory limit: 128 MB

A few friends have decided to do laundry together. They are all very neat, so each day each of the friends wears one clean pair of socks and one clean shirt. The friends have put all dirty socks and shirts to their washing machine. Now they have started to plan how they will dry their laundry. To put this in order, they have decided that:

• every sock will be fastened to the string with a single clothespin,
• each shirt will be fastened with three clothespins,
• one person's socks should all be fastened with clothespins of the same color,
• one person's shirts should all be fastened with clothespins of the same color,
• clothes belonging to different persons may not be fastened with clothespins of the same color,
• apart from that, they wish to use the smallest possible number of clothespin's colors.

Input

The first line of input contains two integers and () denoting the number of friends and the number of clothespins' colors available. The second line contains numbers representing the number of days each friend was collecting laundry (). The third line contains numbers representing the numbers of clothespins of respective colors ().

Output

Your program should output the minimal number of clothespins needed to dry all the laundry. If it is not possible to dry all the laundry in the requested manner, your program should output a single word NIE (i.e., no in Polish).

Example

For the input data:

2 4
3 4
20 10 8 10

the correct result is:

3

whereas for the input data:

3 8
5 4 3
14 14 14 14 14 14 14 14

the correct result is:

NIE

Explanation for the first example: The first person needs 6 clothespins for her socks and 8 clothespins for her shirts. The second person needs 8 clothespins for her socks and 12 clothespins for her shirts. The second person should use the clothespins of the first color both for her socks and her shirts. The first person may then use, e.g., the clothespins of the second and the fourth color.

Task author: Szymon Acedanski.