Friends
(Main file name: friend.pl)

A social network consists of n people numbered 0, ..., n-1. Some people in the network will become friends. If x is a friend of y, then y is a friend of x.

The people are added to the network in n stages, which are also numbered from 0 to n-1. Person i is added in stage i. In stage 0, person 0 is added as the only person of the network. In each of the next stages, a person is added to the network by a host, who may be any person already in the network. At stage i(0<i<n ), the host for that stage can add the incoming person into the network by one of the following three protocols:

After we build the network we would like to pick a sample for a survey, that is, choose a group of people from the network. Since friends usually have similar interests, the sample should not include any pair of people who are friends with each other. Each person has a survey confidence, expressed as a positive integer, and we would like to find a sample with the maximum total confidence.

Input Formats

An input file for LP systems contains the following facts:

Output format

The output should contain exactly one fact of the form max_confidence(K), where K is the largest possible confidence for any sample in the network.

Examples


Input Diagram Output

people(6).

host_protocol(1,0,0).
host_protocol(2,1,0).
host_protocol(3,1,2).
host_protocol(4,2,1).
host_protocol(5,0,0).

confidence(0,13).
confidence(1,3).
confidence(2,6).
confidence(3,20).
confidence(4,10).
confidence(5,15).


max_confidence(35).

people(4).

host_protocol(1,0,0).
host_protocol(2,1,1).
host_protocol(3,2,0).

confidence(0,50).
confidence(1,25).
confidence(2,25).
confidence(3,10).

max_confidence(60).

people(10).

host_protocol(1,0,0).
host_protocol(2,1,0).
host_protocol(3,2,2).
host_protocol(4,3,1).
host_protocol(5,2,0).
host_protocol(6,5,2).
host_protocol(7,3,0).
host_protocol(8,7,0).
host_protocol(9,8,1).

confidence(0,20).
confidence(1,10).
confidence(2,5).
confidence(3,40).
confidence(4,20).
confidence(5,10).
confidence(6,15).
confidence(7,75).
confidence(8,35).
confidence(9,45).


max_confidence(155).