Problem: After waking up at hh:mm, Andrew realised that he had forgotten to feed his only cat for yet another time (guess why there's only one cat). The cat's current hunger level is H points, moreover each minute without food increases his hunger by D points.

At any time Andrew can visit the store where tasty buns are sold (you can assume that is doesn't take time to get to the store and back). One such bun costs C roubles and decreases hunger by N points. Since the demand for bakery drops heavily in the evening, there is a special 20% discount for buns starting from 20:00 (note that the cost might become rational). Of course, buns cannot be sold by parts.

Determine the minimum amount of money Andrew has to spend in order to feed his cat. The cat is considered fed if its hunger level is less than or equal to zero.

Input

The first line contains two integers hh and mm (00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59) — the time of Andrew's awakening.

The second line contains four integers H, D, C and N (1 ≤ H ≤ 105, 1 ≤ D, C, N ≤ 102).

Output

Output the minimum amount of money to within three decimal digits. You answer is considered correct, if its absolute or relative error does not exceed 10 - 4.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if <image>.

Examples

Input

19 00
255 1 100 1


Output

25200.0000


Input

17 41
1000 6 15 11


Output

1365.0000

Note

In the first sample Andrew can visit the store at exactly 20:00. The cat's hunger will be equal to 315, hence it will be necessary to purchase 315 buns. The discount makes the final answer 25200 roubles.

In the second sample it's optimal to visit the store right after he wakes up. Then he'll have to buy 91 bins per 15 roubles each and spend a total of 1365 roubles.

Solution (in JAVA):

Solution:
 import java.io.*;
    import java.util.*;
  
 
  
        public class Codeforces {
    	
    		   public static long log2(long x)
    			{
    				long p=1;
    				long ans=0;
    				while(x>=p)
    				{
    					p*=2;
    					ans++;
    				}
    				return ans-1;
    			}
    		   
    		   
    		   public static void extendedgcd(int a, int b)
    		   {
    			   x=0;
    			   y=0;
    			   gc=0;
    			   xgcd(a,b);
    			   pw.println(a+"*"+x+" + "+b+"*"+y+" = "+gc);
    			   
    		   }
    		   
    		   
    		   public static long modex(long a, long b, long c)
    		   {
    			   if(b==0)
    				   return 1;
    			   else if(b==1)
    				   return a%c;
    			   else if(b%2==0)
    			   {
    				   	return modex((a*a)%c,b/2,c);
    			   }
    			   else
    			   {
    				   return (a*modex((a*a)%c,b/2,c))%c;
    				   
    			   }
    			   
    			   
    		   }
    		   
    		   
    		   public static void xgcd(int a, int b)
    		   {
    			   
    			   if(b==0)
    			   {
    				   x=1;
    				   y=0;
    				   gc=a;
    				   
    				   
    			   }
    			   else
    			   {
    				   xgcd(b,a%b);
    				   int temp = x;
    				   x=y;
    				   y = temp - ((a/b)*y);
    				   
    			   }
    		   }
    		   
    		   public static long gcd(long a, long b)
    		   {
    			   if(b==0)return a;
    			   else return gcd(b,a%b);
    			   
    		   }
    		   
    		   static int x,y,gc;
    		   
    		  
    		
    		   
    		   static HashSet<Character> set;
    		   
    		   
    		   
    		   public static long expmod(long a, long b, long mod)
    		   {
    			   if(b==0)return 1;
    			   if(b==1)return a;
    			   
    			   if(b%2==0)
    			   {
    				   return ((expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
    			   }
    			   else
    			   {
    				   return ((a%mod)*(expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
    			   }
    		   }
    		   
    		   static class Comp implements Comparator<Point>
    		   {

				@Override
				public int compare(Point arg0, Point arg1) {
					
					if(arg0.x>arg1.x)return 1;
					if(arg0.x<arg1.x)return -1;
					return 0;
				}
    			   
    		   }
    		   
    		   
    		   static class STComp implements Comparator<Integer>
    		   {

				@Override
				public int compare(Integer arg0, Integer arg1) {
					
					return arg0.compareTo(arg1); 
				}
    			   
    		   }
    		   
    		   static class Point
    		   {
    			   int x,y,ind;
    			   
    			    public Point(int a, int b)
    			    {
    			    	x=a;
    			    	y=b;
    			    	ind=0;
    			    }
    			   
    			    @Override
    			    public boolean equals(Object o) {
    			 
    			        // If the object is compared with itself then return true  
    			        if (o == this) {
    			            return true;
    			        }
    			 
    			        /* Check if o is an instance of Complex or not
    			          "null instanceof [type]" also returns false */
    			        if (!(o instanceof Point)) {
    			            return false;
    			        }
    			         
    			        // typecast o to Complex so that we can compare data members 
    			        Point c = (Point) o;
    			         
    			        // Compare the data members and return accordingly 
    			        return x==c.x&&y==c.y;
    			                
    			    }
    			    
    		   }
    		   
    		 
    		   
    		  
    		   
    		   public static boolean issub(String s1, String s2)
    		   {
    			   if(s1.length()>s2.length())
    			   return false;
    			   
    			   int l1 = s1.length();
    			   int l2 = s2.length();
    			   
    			   
    			   for(int i=0;i<=l2-l1;i++)
    			   {
    				   String sub = s2.substring(i, i+l1);
    				   if(s1.equals(sub))return true;
    			   }
    			   
    			   return false;
    		   }
    		   
    		   
    		   
    		   public static String enc(String s, int n)
    		   {
    			   String s1 = s.substring(0,n);
    			   String s2 = s.substring(n, s.length());
    			   
    			  String re="";
    			  for(int i=s1.length()-1;i>=0;i--)re+=s1.charAt(i);
    			  
    			  return re+s2;
    			   
    			   
    			   
    		   }
    		 
    		   
    		   
    		   static int vis[];
    		   
    		   public static void dfs(int x)
    		   {
    			   vis[x]=1;
    			   
    			   ArrayList<Integer> li = adj[x];
    			   
    			   for(int ch:li)
    			   {
    				   
    				   if(vis[ch]==0)dfs(ch);
    				   
    			   }
    			   
    		   }
    		   /*
    		   public static void dfsm(int x, HashSet<Integer> set)
    		   {
    			   vis2[x]=1;
    			   
    			   ArrayList<Integer> li = adj[x];
    			   
    			   for(int ch:li)
    			   {
    				   //if(!set.contains(ch))continue;
    				   if(vis2[ch]==0)dfsm(ch,set);
    				   
    			   }
    			   
    		   }
    		   */
    		   
    		  
    		
    		   public static void countPaths(int s, int d, ArrayList<Integer> pa)
    		   {
    			   
    			   vis2[s]=1;
    			   if(s==d)
    			   {
    				   pa.add(s);
    				 //  paths[ct] = new ArrayList<Integer>(pa);
    				   ct++;
    			   }
    			   else
    			   {
    				   ArrayList<Integer> li = adj[s];
    				   pa.add(s);
    				   
    				   for(int ad: li)
    				   {
    					   if(vis2[ad]==0)countPaths(ad,d,pa);
    				   }
    				   
    				   
    			   }
    			   
    			   if(pa.size()>1)pa.remove(pa.size()-1);
    			   vis2[s]=0;
    			   return ;
    		   }
    		  
    		   
    		   
    		   public static boolean dif(String s1, String s2)
    		   {
    			   int ct=0;
    			   if(s1.length()!=s2.length())return false;
    			   for(int i=0;i<s1.length();i++)
    			   {
    				   if(s1.charAt(i)!=s2.charAt(i))ct++;
    				   
    			   }
    			   
    			   if(ct==1)return true;
    			   else return false;
    			   
    			   
    		   }
    		   
    		   
    		   
    		   
    		   static void add(int arr[], int N, int lo,
                       int hi, int val)
    		   {
							    arr[lo] += val;
							    if (hi != N - 1)
							       arr[hi + 1] -= val;
    		   }
 
// Utility method to get actual array from 
// operation array
static void updateArray(int arr[], int N)
{
    // convert array into prefix sum array
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}
  
// method to print final updated array
static void printArr(int arr[], int N)
{
    updateArray(arr, N);
    for (int i = 0; i < N; i++)
        System.out.print(""+arr[i]+" ");
    System.out.print("\n");
}
  
    		   
  
    		  static int cyc;
    		   
    		   
    		  
    		  public static void dfsmod(int v, HashSet<Integer> set)
    		  {
    			  vis2[v]=1;
    			  
    			  ArrayList<Integer> li = adj[v];
    			  
    			  set.add(v);
    			  
    			  for(int ch: li)
    			  {
    				  if(set.contains(ch))
    				  {
    					  cyc=1;
    					  pw.println("** "+ch+" "+v);
    				  }
    				  if(vis2[ch]==0)dfsmod(ch,set);
    				  
    			  }
    			  
    			  set.remove(v);
    			  
    			  
    		  }
    		  
    		  
    		  	public static boolean isps(int x)
    		  	{
    		  		int sq = (int)Math.sqrt(x);
    		  		
    		  		return sq>0&&sq*sq==x;
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  	}
    		  
    		  	 public static void combinations(String suffix,String prefix)
    		  	 {
    		         if(prefix.length()<0)return;
    		         pw.println(suffix);
    		        	 
    		        	 
    		         for(int i=0;i<prefix.length();i++)
    		          combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()));
    		         
    		     }
    		  	
    		  	
    		  	 
    		
    		  	 
    		  	 
    		  	 public static void topo(int x)
    		  	 {
    		  		 vis2[x]=1;
    		  		// pw.println("vis "+x);
    		  		 ArrayList<Integer> li = adj[x];
    		  		// pw.println(x+" has siz "+li.size());
    		  		// Integer i = x;
    		  		 for(int ch: li)
    		  		 {
    		  			
    		  			 if(vis2[ch]==0)
    		  				 {topo(ch);
    		  				//pw.println(x+" "+ch);
    		  				 }
    		  		 }
    		  		 
    		  		 st.push(x);
    		  		 //pw.println(i+" pushed");
    		  	 }
    		  	 
    		  	 
    	  		   

    		 	static  ArrayList<Integer>[] adj;
    		 	static int[] vis2;
    		 	static int ct;

    		     public static void ch(Stack<Integer> s)
    		     {
    		    	 s.push(4);
    		    	 return;
    		     }
    		     
    		     static Stack<Integer> st;
    		     
    		     
    		     static class PQnode implements Comparable<PQnode>
    		     {
    		    	 int value;
    		    	 int distance;
    		    	 
    		    	 public PQnode(int x, int y)
    		    	 {
    		    		 value=x;
    		    		 distance=y;
    		    	 }

					@Override
					public int compareTo(PQnode o) {
					return Integer.compare(this.distance, o.distance);
						
					
					
					}
					
					
					  @Override
		    		    public  boolean equals(Object o)
		    		    {
		    		    	if(o==this)return true;
		    		    	
		    		    	if(!(o instanceof PQnode))
		    		    	{
		    		    		return false;
		    		    	}
		    		    	
		    		    	PQnode node = (PQnode) o;
		    		    	
		    		    	return value==node.value&&distance==node.distance;
		    		    	
		    		    }
    		     }
    		  
    		  
    		     static class Compq implements Comparator<PQnode>
    		     {

					
					public int compare(PQnode arg0, PQnode arg1) {
						
						if(arg0.distance>arg1.distance)return 1;
						if(arg0.distance<arg1.distance)return -1;
						return 0;
					}
    		    	 
    		    	 
    		    	 
    		     }
    		     
    		     public static void printpa(int pa[],int x)
    		     {
    		    	 if(pa[x]==-1)
    		    		 
    		    		 pw.println(x);
    		    	 else
    		    	 {
    		    		 printpa(pa, pa[x]);
    		    		 pw.println(x);
    		    	 }
    		     }
    		     
    		     
    		     static class Node
    		     {
    		    	 int data;
    		    	 Node next;
    		    	 
    		    	 public Node(int x)
    		    	 {
    		    		 data =x;
    		    		 next=null;
    		    	 }
    		     }
    		     
    		     static Node he;
    		     static Node rev(Node n)
    		     {
    		    	 if(n.next==null)
    		    	 {
    		    		he=n;
    		    		return n;
    		    		 
    		    	 }
    		    	 else
    		    	 {
    		    		 Node rt = rev(n.next);
    		    		 rt.next=n;
    		    		 return n;
    		    	 }
    		    	 
    		     }
    		     
    		     
    		     
    		     
    		     public static int trap(final int[] A) {
    		    	    
    		         int n = A.length;
    		         int arr[] = new int[A.length];
    		         for(int i=0;i<A.length;i++)arr[i]=A[i];
    		         int nge[] = new int[A.length];
    		         
    		         Stack<Point> st = new Stack<Point>();
    		         //int ip=0;
    		         
    		        
    		         
    		         st.push(new Point(arr[0],0));
    		         
    		         for(int i=1;i<n;i++)
    		         {
    		             Point p = new Point(arr[i],i);
    		             
    		             while(!st.isEmpty()&&p.x>=st.peek().x)
    		             {
    		                 Point pop = st.pop();
    		                 nge[pop.y]=p.y;
    		             }
    		             st.push(p);
    		             
    		         }
    		         
    		         while(!st.isEmpty())
    		         {
    		             Point p = st.pop();
    		             nge[p.y]=-1;
    		         }
    		         
    		         int ans=0;
    		        for(int i=0;i<n;i++)System.out.print(nge[i]+" ");
    		        pw.println(); 
    		        for(int i=0;i<n;)
    		         {
    		             if(arr[i]!=0)
    		             {
    		                 int ng = nge[i];
    		                 if(ng==-1)
    		                 {
    		                   int j=i+1;
    		                   while(j<n&&arr[j]==0)j++;
    		                   
    		                   if(j!=n)
    		                   {int ad = (j-i-1)*arr[j];
    		                       ans+=ad;
    		                     System.out.println("1* "+i+" "+j+" "+ad);
    		                     i=j;
    		                     
    		                   }
    		                  
    		                   
    		                 }
    		                 else
    		                 {
    		                    int sub=0;
    		                    int j = i+1;
    		                    while(j<n&j<ng)
    		                    {
    		                        sub+=arr[j];
    		                        j++;
    		                    }
    		                    
    		                    int ad = (arr[i]*(ng-i-1))-sub;
    		                    System.out.println("2* "+i+" "+j+" "+ng+" "+ad);
    		                    ans += ad;
    		                    
    		                    i=ng;
    		                     
    		                 }
    		             }
    		             else
    		             {
    		            	 i++;
    		             }
    		         }
    		         
    		         
    		         return ans;
    		         
    		     }
    		     
    		     
    		     
    		     public static int round(int st, int end, int a, int b)
    		     {
    		    	 int mid = (st+end)/2;
    		    	 
    		    	 if(a<=mid&&b>=mid+1)return 0;
    		    	 else
    		    	 {
    		    		 if(a<=mid&&b<=mid)
    		    		 {
    		    			 return 1+round(st,mid,a,b);
    		    			 
    		    		 }
    		    		 else
    		    		 {
    		    			 return 1+round(mid+1,end,a,b);
    		    			 
    		    		 }
    		    		 
    		    	 }
    		    	 
    		    	 
    		    	 
    		     }
    		     
    		     
    		     
    		     public static void main(String[] args) 
    	   {
    		    	
    		    
    		    int hh = sc.nextInt();
    		    int mm = sc.nextInt();
    		    
    		    int h  = sc.nextInt();
    		    int d = sc.nextInt();
    		    int c = sc.nextInt();
    		    int n = sc.nextInt();
    		    
    		    
    		    int maw = (hh*60)+mm;
    		    int md = 20*60;
    		    
    		    if(maw>=md)
    		    {
    		    	
    		    	float co = (float) (0.80*(float)c);
    		    	
    		    	int reqbun = (int) Math.ceil(((float)h/n));
    		    	
    		    	float ans = co*reqbun;
    		    	pw.println(ans);
    		    	
    		    }
    		    else
    		    {
    		    	float cs1=0;
    		    	
    		    	float hungn = (float)h + (d)*(md-maw);
    		    	float co = (float) (0.80*(float)c);
    		    	int reqbun = (int) Math.ceil(((float)hungn/n));
    		    	
    		    	cs1 = reqbun*co;
    		    	
    		    	float cs2=0;
    		    	float hngn2 = h;
    		    	float co2 = c;
    		    	int reqbun2 = (int) Math.ceil(((float)hngn2/n));
    		    	
    		    	cs2 = reqbun2*co2;
    		    	
    		    	pw.println(Math.min(cs1, cs2));
    		    	
    		    }
    		    
    		    	 
    		    	 
    		    	/*int dist = (be-ae)/2;
    		    	
    		    	int ct=0;
    		    	while(dist!=0)
    		    	{
    		    		dist/=2;
    		    		ct++;
    		    	}
    		    	 
    		    	int rn = ct+1;
    		    	
    		    
    		    	
    		    	pw.println(l2);
    		    	
    		    	if(rn==l2)
    		    	{
    		    		pw.println("Final!");
    		    	}
    		    	else
    		    	{
    		    		
    		    		pw.println(rn);
    		    	}
    		    	*/
    		    	
    		    	
    		    	 /*int a[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    		    	 for(int i=0;i<a.length;i++)pw.print(a[i]+" ");
    		    	 pw.println();
    		    	 trap(a);*/
    		    	 
    		    	 /*
    		    	 int n = sc.nextInt();
    		    	 int a  = sc.nextInt();
    		    	 int b = sc.nextInt();
    		    	 long sum=0;
    		    	 
    		    	 int arr[] = new int[n];
    		    	 
    		    	 for(int i=0;i<n;i++)
    		    	 {	 arr[i]=sc.nextInt();
    		    	 	sum+=arr[i];
    		    	 }
    		    	 
    		    	 
    		    	 int as = (arr[0]*a)/b;
    		    	 
    		    	 int bl[] = new int[n-1];
    		    	 
    		    	 for(int i=1;i<n;i++)
    		    	 {
    		    		 bl[i-1]=arr[i];
    		    	 }
    		    	 
    		    	 Arrays.sort(bl);
    		    	 
    		    	 if(sum<=as)
    		    	 {
    		    		 pw.println(0);
    		    		 pw.close();
    		    		 return;
    		    	 }
    		    	 
    		    	 int ans=0;
    		    	 for(int i=n-2	;i>=0;i--)
    		    	 {
    		    		 sum = sum-bl[i];
    		    		 ans++;
    		    		 if(sum<=as)break;
    		    		 
    		    	 }
    		    		 pw.println(ans);
    		    	 
    		    	 */
    		    			 
    		    			 
    		    	 
    		    	 
    		    	 
    		    	 

    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    			 
    		    	 
    		    	 
    		    	 
    		    	
    		    	//pw.println(ans);
    		    	 
    		    	 /*int n  =sc.nextInt();
    		  		int k = sc.nextInt();
    		  		
    		  		int arr[] = new int[n];
    		  		
    		  		for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    		  		
    		  		int pref[] =  new int[n];
    		  		
    		  		for(int i=0;i<n;i++)
    		  		{
    		  			if(i==0)
    		  			{
    		  				pref[i]=arr[i];
    		  			}
    		  			else
    		  			{
    		  				pref[i]=pref[i-1]+arr[i];
    		  			}
    		  		}
    		  				
    		  		double ans = Float.MIN_VALUE;
    		  		
    		  		
    		  		
    		  		for(int i=k;i<=n;i++)
    		  		{
    		  			
    		  			int p1 = 0;
    		  			int p2= i-1;
    		  			
    		  			while(p2<=n)
    		  			{
    		  				//pw.println("calc "+p1+" "+p2);
    		  				double rsum = (p1==0)?pref[p2]:pref[p2]-pref[p1-1];
    		  				double avg = rsum/i;
    		  				//pw.println(i);
    		  				ans = Math.max(ans, avg);
    		  				p1++;
    		  				p2++;
    		  				//pw.println("********");
    		  				if(p2==n)break;
    		  			}
    		  			
    		  		}
    		    	 
    		  		pw.println(ans);
    		    	 */
    		    	 
    		    	 /*
    		    	 */
    		    	
    		    	
    		    	
    		    	/* 
    		    	Node n1 = new Node(1);
    		    	Node n2 = new Node(2);
    		    	Node n3 = new Node(3);
    		    	n1.next=n2;
    		    	n2.next=n3;
    		    	n3.next=null;
    		    	
    		    	rev(n1);
    		    	
    		    	while(he!=null)
    		    	{
    		    		pw.println(he.data);
    		    		he=he.next;
    		    	}
    		    	 */
    		    	 /* 
    		    	int n = sc.nextInt();
    		  		 
    		  		int x = sc.nextInt();
    		  		int y = sc.nextInt();
    		  		
    		  		String st = sc.nextLine();
    		  		int ind[] = new int[n];
    		  		int indct=0;
    		  		for(int i=0;i<st.length();i++)
    		  		{
    		  			if(st.charAt(i)=='1')
    		  			{
    		  				ind[indct++]=i;
    		  			}
    		  			
    		  		}
    		  		
    		  		
    		  		int r=0;
    		  		if(indct==0||indct==1)
    		  		{
    		  			if(indct==0)
    		  			{
    		  				pw.println(y);
    		  				pw.close();
    		  				return;
    		  			}
    		  			else
    		  			{
    		  				r=1;
    		  			}
    		  		}
    		  		
    		  		
    		  		else
    		  		{
    		  		
    		  		for(int i=0;i<indct-1;i++)
    		  		{
    		  			if(ind[i+1]-ind[i]>1)r++;
    		  		}
    		  		
    		  		if(r==0)
    		  		{
    		  			if(r==0)
    		  			{
    		  				pw.println(0);
    		  				pw.close();
    		  				return;
    		  			}
    		  			
    		  		}
    		  		
    		  		r++;
    		  		
    		  		}
    		  		
    		  		
    		  		//pw.println("r "+r);
    		  		
    		  		
    		  		long ans = Long.MAX_VALUE;
    		  		
    		  		for(int rev=0;rev<=r;rev++)
    		  		{
    		  			long left = r-rev;
    		  			long p = (left+1)*y + x*rev;
    		  			//pw.println(" p "+p);
    		  			ans = Math.min(p, ans);
    		  		}
    		  		
    		  		
    		  		pw.println(ans);
    		  		 */
    		  			
    		  				
    		  		 
    		  		 /*PriorityQueue<PQnode> pq = new PriorityQueue<PQnode>();
    		  		
    		  		 pw.println(pq.size());
    		  		 
    		  		 pq.add(new PQnode(1,2));
    		  		 pq.add(new PQnode(3,4));
    		  		 
    		  		 pw.println(pq.size());
    		  		pq.remove(new PQnode(1,2));
    		  		 pw.println(pq.size());
    		  		 
    		  		 
    		  		 
    		  		 int parent[] = new int[4];
    		  		 Arrays.fill(parent, -1);
    		  		 ArrayList<Point> adj[] = new ArrayList[4];
    		  		 
    		  		 for(int i=0;i<4;i++)adj[i] = new ArrayList<Point>();
    		  		 
    		  		 adj[0].add(new Point(1,10));
    		  		 adj[0].add(new Point(2,20));
    		  		 
    		  		 adj[1].add(new Point(0,10));
    		  		adj[1].add(new Point(2,5));
    		  		adj[1].add(new Point(3,16));
    		  		
    		  		adj[2].add(new Point(0,20));
    		  		adj[2].add(new Point(1,5));
    		  		adj[2].add(new Point(3,20));
    		  		
    		  		adj[3].add(new Point(1,16));
    		  		adj[3].add(new Point(2,20));
    		  		 
    		  		 
    		  		 
    		  		 PriorityQueue<PQnode> pq = new PriorityQueue<PQnode>(new Compq());
    		  		 HashSet<Integer> pres = new HashSet<Integer>();
    		  		 
    		  		 int[] dist = new int[4];
    		  		 
    		  		 for(int i=0;i<4;i++)
    		  		 {
    		  			 if(i==0)
    		  			 {
    		  				pq.add(new PQnode(i,0)); 
    		  				dist[i]=0;
    		  			 }
    		  			 else
    		  			 {
    		  				 pq.add(new PQnode(i,Integer.MAX_VALUE));
    		  				 dist[i]=Integer.MAX_VALUE;
    		  			 }
    		  			 pres.add(i);
    		  			 
    		  		 }
    		  		 
    		  		 
    		  		 while(!pq.isEmpty())
    		  		 {
    		  			 PQnode pop = pq.poll();
    		  			 pres.remove(pop.value);
    		  			// pw.println(pop.value+" "+pop.distance);
    		  			 dist[pop.value]=pop.distance;
    		  			 for(Point p: adj[pop.value])
    		  			 {
    		  				 if(pres.contains(p.x))
    		  				 {
    		  					 if(p.y+dist[pop.value]<dist[p.x])
    		  					 {
    		  						 pw.println("ha");
    		  						
    		  						 pq.remove(new PQnode(p.x,dist[p.x]));
    		  						 dist[p.x]=p.y+dist[pop.value];
    		  						 pq.add(new PQnode(p.x,p.y+dist[pop.value]));
    		  						 parent[p.x]=pop.value;
    		  					 }
    		  				 }
    		  			 }
    		  			 
    		  		 }
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 for(int i=0;i<4;i++)pw.print(dist[i]+" ");
    		  		pw.println();
    		  		 printpa(parent, 3	);
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 Dijkstra over.
    		  		 */
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 /*
    		  		st = new Stack<Integer>();
    		  		 
    			 
    			  cyc=0;
       			adj = new ArrayList[4];
       			vis2 = new int[4];
       			
       			Arrays.fill(vis2, 0);
       			for(int i=0;i<4;i++)adj[i] = new ArrayList<Integer>();
       			   
       			
       			adj[0].add(1);
       			adj[0].add(2);
       			adj[0].add(3);
       			
       			adj[1].add(3);
       			
       			//adj[2].add(0);
       			adj[2].add(1);
    			   //adj[3].add(2);
    			   
       			st = new Stack<Integer>();
    			
       			topo(0);
    			   
    			 while(!st.isEmpty())pw.println(st.pop());
    			 */
    				 
    			/*
    			int n = sc.nextInt();
    			
    			int arr[] = new int[n];
    			
    			for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    			
    			long ansg =0,ansv = Long.MAX_VALUE; 
    			
    			int arr2[] = new int[n];
    			for(int i=0;i<n;i++)arr2[i]=arr[i]-i;
    		
    			for(int i=0;i<n;i++)
    			{
    				int x = arr2[i];
    				
    				if(x<=0)
    				{
    					
    					if(i<ansv)
    					{
    						
    						ansg=i;
    						ansv=i;
    					}
    				}
    				else
    				{
    					float t = ((float)x)/n;
    					long tt = (long)Math.ceil(t);
    					
    					long ex = i;
    					long ti = tt*n+ex;
    					
    					
    					if(ti<ansv)
    					{
    						//pw.println("** "+i);
    						ansg=i;
    						ansv=ti;
    					}
    					
    				}
    				
    				
    				
    			}
    			
    			pw.println(ansg+1);
    			*/
    			   
    			   
    			   
    		
    			   
    			   
    	
    			   
    			   /*ct=0;
    			
    			paths= new ArrayList[10];
    			adj = new ArrayList[4];
    			vis2 = new int[4];
    			
    			for(int i=0;i<4;i++)adj[i] = new ArrayList<Integer>();
    			   
    			for(int i=0;i<10;i++)paths[i] = new ArrayList<Integer>();
    			
    			adj[0].add(1);
    			adj[0].add(2);
    			adj[0].add(3);
    			
    			adj[1].add(3);
    			
    			adj[2].add(0);
    			adj[2].add(1);
    			
    			countPaths(2,3, new ArrayList<Integer>());
    			pw.println(ct);
    			   
    			for(int i=0;i<ct;i++)pw.println(paths[i]);
    			  */ 
    			   
    			   
    			   
    			   /*
    			   int n = sc.nextInt();
    			int m = sc.nextInt();
    			
    			int arr[] = new int[n];
    			
    			for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    			
    			int req = n/m;
    			
    			int[] rem = new int[m];
    			
    			
    			HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    			for(int i=0;i<n;i++)
    			{
    				rem[arr[i]%m]++;
    				
    			}
    			int li=-1;
    			long ans=0;
    			for(int i=0;i<m;i++)
    			{
    				if(rem[i]>=req)
    				{
    					rem[(i+1)%m]+=rem[i]-req;
    					ans+=(rem[i]-req);
    				}
    				else
    				{
    					li=i;
    					
    				}
    			}
    			
    			for(int i=0;i<li;i++)
    			{
    				if(rem[i]>=req)
    				{
    					rem[(i+1)%m]+=rem[i]-req;
    					ans+=(rem[i]-req);
    				}
    				else
    				{
    					li=i;
    					
    				}
    			}
    			pw.println(ans);
    			*/
    			
    			
    			
    			   //pw.println(pa);
    		/*	  NGE 
       		int[] sto = {100,80,60,70,60,75,85};
       		int n = sto.length;
       		
       		int[] spa = new int[n];
       		spa[0]=1;
       		
       		Stack<Integer> st = new Stack<Integer>();
       		st.push(0);
       		
       		for(int i=1;i<n;i++)
       		{
       			
       			while(!st.isEmpty()&&sto[st.peek()]<=sto[i])st.pop();
       			
       			spa[i]=(st.isEmpty())?i+1:i-st.peek();
       			st.push(i);
       			
       		}
    			  
       		
       		for(int i=0;i<n;i++)pw.print(sto[i]+" ");
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(spa[i]+" ");
    			  
    			   
    			   int[] nge = new int[n];
    			   
    			   st.clear();
    			   Stack<Point> st2 = new Stack<Point>();
    			   st2.push(new Point(sto[0],0));
    			   
    			   for(int i=1;i<n;i++)
    			   {
    				   while(!st2.isEmpty()&&st2.peek().x<sto[i])
    				   {
    					   Point pop = st2.pop();
    					   nge[pop.y]=sto[i];
    				   }
    				   st2.push(new Point(sto[i],i));
    				   
    			   }
    			   
    			   while(!st2.isEmpty())
    			   {
    				   nge[st2.pop().y]=-1;
    			   }
    			  
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(sto[i]+" ");
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(nge[i]+" ");
    			 */ 
    			   
    			   /*  int r = 2000000000;
    			  pw.println(r);
    			int n = sc.nextInt();
    			int k = sc.nextInt();
    			int l = sc.nextInt();
    			int m = n*k;
    			int arr[] = new int[m];
    			
    			for(int i=0;i<m;i++)arr[i]=sc.nextInt();
    			
    			Arrays.sort(arr);
    			
    			int limit = l+arr[0];
    			int li=-1;
    			
    			for(int i=0;i<m;i++)
    			{
    				//pw.println(arr[i]);
    				if(arr[i]>limit)
    				{
    					//pw.println(arr[i]);
    					li=i; break;
    				}
    			}
    			//pw.println(limit+" "+li);
    			if(li==-1)li=n;
    			
    			int noofsmallest = li;
    			
    			if(noofsmallest<n)
    			{
    				pw.println(0);
    			}
    			else
    			{
    				li--;
    				long ans=0;
    				for(int i=0;i<n-1;i++)
    				{
    					ans+=(long)arr[li];
    					li--;
    				}
    				ans+=arr[0];
    				pw.println(ans);
    				
    			}
    			  */ 
    			   
    			   
    			   
    		
    			 
    			  
    			pw.close();  
    			   
    	   }
    		   
    		   
    		   
    		   static  class MyScanner 
    			{
    	
    			BufferedReader br;
    			StringTokenizer st;
    	
    			public MyScanner() 
    			{
    				br = new BufferedReader(new InputStreamReader(System.in));
    			}
    	
    			String next() 
    			{
    				
    				while (st == null || !st.hasMoreElements()) 
    				{
    					try 
    					{
    						st = new StringTokenizer(br.readLine());
    					} catch (IOException e) 
    					{
    						e.printStackTrace();
    					}
    				}
    				return st.nextToken();
    			}
    	
    			int nextInt() 
    			{
    				return Integer.parseInt(next());
    			}
    	
    			long nextLong() 
    			{
    				return Long.parseLong(next());
    			}
    	
    			double nextDouble() 
    			{
    				return Double.parseDouble(next());
    			}
    	
    			String nextLine()
    			{
    				String str = "";
    				try 
    				{
    					str = br.readLine();
    				} catch (IOException e) 
    				{
    					e.printStackTrace();
    				}
    				return str;
    			}
    	
    		}
    	
    		static MyScanner sc = new  MyScanner();
    		static PrintWriter pw = new PrintWriter(System.out, true);
    		
    		static class DisjointSet
    		{
    			int[] parent;
    			int[] rank;
    			int n;
    			
    			public DisjointSet(int x)
    			{
    				n=x;
    				parent = new int[x];
    				rank = new int[x];
    				
    				for(int i=0;i<n;i++)
    				{
    					parent[i]=i;
    				}
    				
    			}
    			
    			public int find(int x)
    			{
    				
    				if(parent[x]==x)
    					return x;
    				else 
    					return find(parent[x]);
    			}
    			
    			public void union(int i, int j)
    			{
    				int iroot = find(i);
    				int jroot = find(j);
    				
    				if(iroot==jroot)
    					return;
    				
    				if(rank[iroot]<rank[jroot])
    				{
    					parent[iroot]=jroot;
    					
    				}
    				else if(rank[jroot]<rank[iroot])
    				{
    					parent[jroot]=iroot;
    				}
    				else
    				{
    					parent[iroot]=jroot;
    					rank[jroot]++;
    					
    				}
    				
    				
    				
    				
    			}
    			
    			
    			
    			
    			
    		}
    	
    		
    	}