Minibus driver Sergey A. Greedson has become totally famous for his phenomenal greediness. He claimed time and again that he held himself in readiness to throttle his brother and sell out all friends for an extra cent. Unfortunately, these statements were impossible to verify because Sergey had got neither brothers nor friends, home or family. And he had not got any money either. An old minibus seemed to be the only property of Mr. Greedson. So he traveled the city giving occasional passengers a lift and sometimes examining pavements for dumps...

One day the heavens took pity on Sergey and decided to stop his useless being in out cruel world. For this noble purpose an axe fell down on the head of carefree Mr. Greedson, who had just left the minibus on account of inviting shine of a 5-ruble coin. The dreams of profitable bottle sale went out of his head in a blink replaced by the axe. In a figurative sense, of course. Heavens tool could not break a stiff skull of Mr. Greedson but, as it turned out later, gave him several rather useful abilities.

Soon after the axe was sold, Sergey discovered his ability to foresee the future. What a scope, what a prospect was given to the artless minibus driver! Who are we and where are we going? What is to be feared and hoped? The answers for these questions did not worry Mr. Greedson at all. But Sergey's greedy mind was clever enough to use his new ability to earn some money while doing his usual job.

Every day the minibus makes a passage from 1-st to N-th bus stop. There are M passenger seats in the minibus. Once in the evening Mr. Greedson has counted the probability lines and found out that the next day K persons would wait for the minibus on the bus stops. For each person the number of bus stop S[i], where he wants to get into the minibus, and the number of bus stop F[i], where he is going to leave the minibus, were found. According to Sergey's pricing policy, each passenger must pay P dollars for a ticket despite the number of passed bus stops. More over, at a bus stop Mr. Greedson may allow some persons to get into the minibus and ban others (in other words, he may choose his passengers himself). After the problem was posed to maximize the gain, Sergey decided to find the persons who should be allowed to get into the minibus. Unfortunately, he does not possess enough power to perform it. And what about you?

The first line contains integer numbers N (2 ≤ N ≤ 100000), M (1 ≤ M ≤ 1000), K (0 ≤ K ≤ 50000) and P (1 ≤ P ≤ 10000). Each of the next K lines contains the integer numbers S[i] and F[i] (1 ≤ S[i] < F[i] ≤ N) for the corresponding passenger.

The first line should contain the maximal gain. The second line should contain the numbers of persons, who should be allowed to get into the minibus to obtain this gain. The numbers should be listed in any order and separated by single spaces. If the problem has several solutions, you should output any of them.